作者：爱塔居

专栏：数据结构​​​​​​

作者简介：大三学生，希望和大家一起进步！

目录

前言

1. 检查两棵树是否相同。 

2. 另一颗树的子树。

3. 翻转二叉树。

4. 判断一颗二叉树是否是平衡二叉树。

5. 对称二叉树。

前言

前面两章介绍了二叉树的基本概念，我们今天开始做一些题目吧。在练习的过程中，我们加深对二叉树的了解，学会二叉树的简单应用。

1. 检查两棵树是否相同。 

力扣

思路：判断两棵树是否相同，判断的是结构和val值。

1.两个都为空，相同

2.一个为空，一个不为空，不相同

3.两个都不为空，不一定相同，需要判断val值。

利用递归解题。

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p==null&q==null){return true;}if(p==null&&q!=null||p!=null&&q==null){return false;} if(p.val!=q.val){return false;}
return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}}

2. 另一颗树的子树。

力扣

思路：我们利用第一道题的方法，判断二叉树是否相同。

如果两棵二叉树，有一棵是空，subRoot就不是root的子树，返回false;

如果，两棵二叉树相同，返回true；

如果两棵二叉树不相同，判断root的左子树是否和subRot相同，相同返回true；，不相同判断root的左子树与subRot是否相同。

class Solution {public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root==null||subRoot==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){return true;}if(p==null&&q!=null||p!=null&&q==null){return false;} if(p.val!=q.val){return false;}
return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}
}

3. 翻转二叉树。
 力扣

思路：如果二叉树为空，就不用翻转了。

如果不为空，先用一个temp装root.left,将左右二叉树进行翻转。接着，通过递归翻转左子树，再翻转右子树。

class Solution {public TreeNode invertTree(TreeNode root) {if(root==null){return null;}TreeNode temp=root.left;root.left=root.right;root.right=temp;invertTree(root.left);invertTree(root.right);return root;}
}

4. 判断一颗二叉树是否是平衡二叉树。
力扣

思路是对二叉树做先序遍历，从底至顶返回子树最大高度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。

class Solution {public boolean isBalanced(TreeNode root) {return recur(root)!=-1;}public int recur(TreeNode root){if(root==null){return 0;}int left=recur(root.left);if(left==-1){return -1;}int right=recur(root.right);if(right==-1){return -1;}return Math.abs(left-right)<=1?Math.max(left,right)+1:-1;}
}

 5. 对称二叉树。

 力扣

思路：判断整棵树是不是轴对称，要判断这棵树的左子树和这棵树的右子树是不是对称的，那就要判断左子树的左树和右子树的右树，左子树的右数和右子树的左树。

class Solution {public boolean isSymmetric(TreeNode root) {return isSymmetricChild(root,root);}public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree){
if(leftTree==null&&rightTree==null)return true;
if(leftTree==null||rightTree==null)return false;
return (leftTree.val==rightTree.val)&&(isSymmetricChild(leftTree.left,rightTree.right))&&(isSymmetricChild(leftTree.right,rightTree.left));}}