利用子问题思路解决二叉树相关Oj题
目录
检查两棵树是否相同：题目链接
判断另⼀棵树的子树是否存在：题目链接
翻转二叉树：题目链接
判断⼀棵二叉树是否是平衡二叉树：题目链接
判断对称二叉树：题目链接
二叉树的层序遍历
二叉树的分层遍历：题目链接
判断一棵树是否为完全二叉树：
检查两棵树是否相同：题目链接
代码实现：
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q != null || q == null && p != null) {
return false;
}
if(p == null && q == null) {
return true;
}
if(p.val != q.val) {
return false;
}
return isSameTree(q.left,p.left) && isSameTree(q.right,p.right);
}题解思路：
首先，第一个 if 判断两个根结点是否为一个为空，一个不为空，如果是的话说明以当前根结点p和q肯定不是相同的树，直接返回false。
其次，到了第二个 if 判断，p和q只剩下两种情况，要么都为空，要么都不为空，第二个 if 判断当前结点是否都为空的情况，如果是，说明是以当前 p 和 q 结点作为根的树是一样的，返回true。
最后，剩下p 和 q 都不为空的情况，如果 p 和 q 当中 的值不一样，返回false；如果p 和 q 里的值相同，执行到最后一句时，如果当前的 根左子树 和右子树相同的话，就会返回true了。
判断另⼀棵树的子树是否存在：题目链接
代码实现：
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
if(root == null) {
return false;
}
if(isSameTree(root,subRoot)) {
return true;
}
if(isSubtree(root.left,subRoot)) {
return true;
}
if(isSubtree(root.right,subRoot)) {
return true;
}
return false;
}
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q != null || q == null && p != null) {
return false;
}
if(p == null && q == null) {
return true;
}
if(p.val != q.val) {
return false;
}
return isSameTree(q.left,p.left) && isSameTree(q.right,p.right);
}题解思路：
首先，判断当前会移动的结点root，如果是空，返回false；
第一个 if 我们利用了上题的代码来判断当前两棵树是否一样，一样则返回true；
第二个 if 和 第三个 if 分别往 当前结点的 左子树 和右子树 走，并分别判断当前的root和subRoot颗树是否相同 。
最后，如果都没有找到，只能返回false。
翻转二叉树：题目链接
代码实现：
public TreeNode invertTree(TreeNode root) {
if(root == null) {
return null;
}
TreeNode num = root.left;
root.left = root.right;
root.right = num;
invertTree(root.left);
invertTree(root.right);
return root;
}题解思路：
只要把每个结点的左子树和右子树交换就可以了。
判断⼀棵二叉树是否是平衡二叉树：题目链接
代码实现：
public boolean isBalanced(TreeNode root) {
if(root == null) {
return true;
}
int left = getHight(root.left);
int right = getHight(root.right);
return Math.abs(left-right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
public int getHight(TreeNode root) {
if(root == null) {
return 0;
}
int left = getHight(root.left);
int right = getHight(root.right);
return left > right ? left + 1 : right + 1;
}题解思路：
首先，如果当前结点为空，也认为是平衡二叉树；
其次，分别求得当前结点的左子树 和 右子树 的高度。
如果当前结点的左子树和右子树高度差 不大于 1 ，并且，当前结点的左子树 是平衡二叉树，结点的右子树也是平衡二叉树，才能说明这棵树为平衡二叉树。
判断对称二叉树：题目链接
代码实现：
public boolean isSymmetric(TreeNode root) {
if(root == null) {
return true;
}
return isSymmetrichild(root.left,root.right);
}
public boolean isSymmetrichild(TreeNode leftroot,TreeNode rightroot) {
if(leftroot == null && rightroot != null || leftroot != null && rightroot == null) {
return false;
}
if(leftroot == null && rightroot == null) {
return true;
}
if(leftroot.val != rightroot.val) {
return false;
}
return isSymmetrichild(leftroot.left,rightroot.right) &&
isSymmetrichild(leftroot.right,rightroot.left);
}题解思路：
首先，如果根结点为空，也当作是平衡二叉树。
我们创建另外的方法 isSymmetrichild 方法来判断平衡二叉树，把根结点的左子树的根和右子树的根传过去当作参数。
判断逻辑先从当前两个结点是否为一空一不空，再判断是否都为空，最后剩下就是两个结点不为空了，再判断里面的值。
到最后，在当前两个结点的值相同的情况下，如果leftroot的左子树 与 rightroot的右子树相同，并且leftroot的右子树 与 rightroot的左子树相同，才能说明当前的两个结点是对称的树。
二叉树的层序遍历
这是为下面的二叉树的分层遍历这道题作个铺垫理解，层序遍历也就是要把二叉树的数据从根节点开始，从上到下，从左到右依次遍历。
代码实现：
public void CengXu(TreeNode root) {
if(root == null) {
return;
}
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while( !que.isEmpty()) {
TreeNode cur = que.poll();
System.out.print(cur.val+" ");
if(cur.left != null) {
que.offer(cur.left);
}
if(cur.right != null) {
que.offer(cur.right);
}
}
}分析：
我们利用了一个队列，先把根节点放到队列里，然后再出队列用 cur 承接并打印数据，再判断当前的 cur 得到的 结点 左和右结点是否不为空，不为空则把 当前 cur 结点的左孩子和右孩子放到队列里。再重复此操作。
当最后队列为空时，说明已经分层遍历完了，代码结束。
二叉树的分层遍历：题目链接
代码实现：
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
if(root == null) {
return list;
}
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while( !que.isEmpty()) {
List<Integer> num = new ArrayList<>();
int size = que.size();
while(size != 0) {
TreeNode cur = que.poll();
num.add(cur.val);
if(cur.left != null) {
que.offer(cur.left);
}
if(cur.right != null) {
que.offer(cur.right);
}
size--;
}
list.add(num);
}
return list;
}题解思路：
在 二叉树的层序遍历 的基础上，这是把树的每一层都分开来 一层一层遍历，所以初始化了 list 作为 结果的 总体，而 num 作为 每一层 的数据给到 list 。
我们可以定义一个 size 接收 每次 while（size ！= 0）结束后 队列里的个数，从而得到下一层的数据，以此类推。
并且每一次 while（size ！= 0）循环结束后把该层的数据放到 list 里。
判断一棵树是否为完全二叉树：
代码实现：
public boolean gettrue(TreeNode root) {
if(root == null) {
return true;
}
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while(!que.isEmpty()) {
TreeNode cur = que.poll();
if(cur != null) {
que.offer(cur.left);
que.offer(cur.right);
}else {
break;
}
}
while(!que.isEmpty()) {
TreeNode cur = que.peek();
if(cur == null) {
que.poll();
}else {
return false;
}
}
return true;
}题解思路：
首先，与二叉树的层序遍历类似，把结点放进队列里，不同的是，不用判断当前的 cur 左子树结点 和右子树结点是否为空了，而是判断当前 cur 本身，cur如果不为空 则把 cur的左子树结点 和右子树结点都放到队列里，null 也是可以放到队列里的。当弹出结点元素时遇到 null 则 跳出循环。
最后的循环可以判断是否为二叉树，因为前面把所有的结点包括 null 都放到队列里了，如果是完全二叉树，当第一个循环结束break后，队列里剩下的都应该是 null ，如果不是完全二叉树，则会break后在队列里留了结点元素。
所以，最后的循环判断如果遇到了结点元素，直接返回false。