自己设计商标logo软件安卓优化大师官方版本下载
目录
104.二叉树的最大深度
100.相同的树
226.翻转二叉树
101.对称二叉树
105.从前序与中序遍历序列构造二叉树
106.从中序与后序遍历序列构造二叉树
117.填充每个节点的下一个右侧节点指针Ⅱ
104.二叉树的最大深度
题意：
给定一个二叉树
root，返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
【输入样例】
root=[3,9,20,null,null,15,7]
【输出样例】
3
解题思路：递归
class Solution {public int maxDepth(TreeNode root) {if(root == null){return 0;}//1是当树的根节点不为空时，加上根return 1 + Math.max(maxDepth(root.right),maxDepth(root.left));}
}时间： 击败了100.00%
内存： 击败了36.81%
100.相同的树
题意：
给你两棵二叉树的根节点
p和q，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
【输入样例】
p=[1,2,3], q=[1,2,3]
【输出样例】
true
解题思路：递归
1.先判断当前根节点的值是否一样
2.再判断是否都拥有左子树和右子树
3.递归判断左子树，右子树
class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p == null && q == null){return true;}//如果说两者都会null，会在上面的分支语句返回true//这里判断的是只有一方为null的情况下if(p == null || q == null){return false;}//根都不为null，判断值是否相同if(p.val != q.val){return false;}return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}
}时间： 击败了100.00%
内存： 击败了41.80%
226.翻转二叉树
题意：
给你一棵二叉树的根节点
root，翻转这棵二叉树，并返回其根节点。
【输入样例】
root = [4,2,7,1,3,6,9]
【输出样例】
[4,7,2,9,6,3,1]
解题思路：递归
1. 不断将当前节点的左右子树交换，递归实现
class Solution {public TreeNode invertTree(TreeNode root) {if(root == null){return root;}//左右子树交换TreeNode temp = root.right;root.right = root.left;root.left = temp;//交换左子树invertTree(root.left);//交换右子树invertTree(root.right);return root;}
}时间： 击败了100.00%
内存： 击败了88.10%
101.对称二叉树
题意：
给你一个二叉树的根节点
root， 检查它是否轴对称。
【输入样例】
root = [1,2,2,3,4,4,3]
【输出样例】
true
解题思路：递归
1. 递归函数判断节点的左子树和右子树是否对称；把左子树和右子树拆开，题目就转变成了判断相同的树了。
class Solution {public boolean isSymmetric(TreeNode root) {if(root == null){return true;}return cmp(root.left, root.right);}public boolean cmp(TreeNode root1, TreeNode root2){if(root1 == null && root2 == null){return true;}if(root1 == null || root2 == null || root1.val != root2.val){return false;}return cmp(root1.left,root2.right) && cmp(root1.right,root2.left);}
}时间： 击败了100.00%
内存： 击败了82.85%
105.从前序与中序遍历序列构造二叉树
题意：
给定两个整数数组
preorder和inorder，其中preorder是二叉树的先序遍历，inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点。
【输入样例】
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
【输出样例】
[3,9,20,null,null,15,7]
解题思路：
1. 先序遍历的过程是：根 左 右；中序遍历的过程是：左 根 右。
2. 根据规律，首先需要找到的是根节点，inorder数组中根左边的是左子树，根右边的是右子树；
3. 之后分别构造左子树和右子树；
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {private Map<Integer,Integer> indexMap;public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;//一共n个节点//构造哈希映射，快速定位根节点indexMap = new HashMap<Integer,Integer>();for(int i=0;i<n;i++){indexMap.put(inorder[i],i);}return myBuildTree(preorder,inorder,0,n-1,0,n-1);}public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {if (preorder_left > preorder_right) {return null;}//前序遍历找到根节点int preorder_root = preorder_left;//中序遍历定位根节点int inorder_root = indexMap.get( preorder[preorder_root]);//建立根节点TreeNode root = new TreeNode(preorder[preorder_root]);//确定左子树节点数目int size_left_subtree = inorder_root - inorder_left;//递归构造左子树，连接到根节点root.left = myBuildTree(preorder,inorder,preorder_left+1,preorder_left+size_left_subtree,inorder_left, inorder_root-1);//递归构造右子树root.right = myBuildTree(preorder,inorder,preorder_left+size_left_subtree+1, preorder_right,inorder_root+1, inorder_right);return root;}
}时间： 击败了99.18%
内存： 击败了23.53%
106.从中序与后序遍历序列构造二叉树
题意：
给定两个整数数组
inorder和postorder，其中inorder是二叉树的中序遍历，postorder是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
【输入样例】
inorder = [9,3,15,20,7]，postorder = [9,15,7,20,3]
【输出样例】
[3,9,20,null,null,15,7]
解题思路：
1. 中序遍历的过程是：左 根 右; 后序遍历的过程是：左 右 根 ；。
2. 根据规律，首先需要找到的是根节点，inorder数组中根左边的是左子树，根右边的是右子树；
3. 之后分别构造左子树和右子树；
class Solution {private Map<Integer,Integer> indexMap;public TreeNode buildTree(int[] inorder, int[] postorder) {int n = postorder.length;//一共n个节点//构造哈希映射，快速定位根节点indexMap = new HashMap<Integer,Integer>();for(int i=0;i<n;i++){indexMap.put(inorder[i],i);}return myBuildTree(inorder,postorder,0,n-1,0,n-1);}public TreeNode myBuildTree(int[] inorder,int[] postorder, int inorder_left, int inorder_right,int postorder_left, int postorder_right) {if (postorder_left > postorder_right || inorder_left > inorder_right) {return null;}//后序遍历找到根节点int postorder_root = postorder[postorder_right];//中序遍历定位根节点int inorder_root = indexMap.get(postorder_root);//建立根节点TreeNode root = new TreeNode(postorder_root);//确定左子树节点数目int size_left_subtree = inorder_root - inorder_left;//递归构造左子树，连接到根节点root.left = myBuildTree(inorder, postorder, inorder_left, inorder_root-1,postorder_left,postorder_left+size_left_subtree-1);//递归构造右子树root.right = myBuildTree(inorder,postorder, inorder_root+1, inorder_right,postorder_left+size_left_subtree,postorder_right-1);return root;}
}时间： 击败了99.21%
内存： 击败了61.89%
117.填充每个节点的下一个右侧节点指针Ⅱ
题意：
给定一个二叉树：
struct Node {int val;Node *left;Node *right;Node *next; }填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为
NULL。初始状态下，所有 next 指针都被设置为
NULL。
【输入样例】
root=[1,2,3,4,5,null,7]
【输出样例】
[1,#,2,3,#,4,5,7,#]
解题思路：
利用宽度优先搜索完成本题
/*
// Definition for a Node.
class Node {public int val;public Node left;public Node right;public Node next;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, Node _left, Node _right, Node _next) {val = _val;left = _left;right = _right;next = _next;}
};
*/class Solution {public Node connect(Node root) {if(root== null){return root;}//队列存储节点信息Queue<Node> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()){//每一层的数量int levelCount = queue.size();//前一个节点Node pre = null;for(int i=0;i<levelCount;++i){//出队Node node = queue.poll();if(pre != null){//不是第一个节点pre.next = node;}pre = node;//查看左右节点是否为空，不空入队if(node.left != null){queue.add(node.left);}if(node.right != null){queue.add(node.right);}}}return root;}
}时间： 击败了76.40%
内存： 击败了5.16%