1. 检查两棵树是否相同
题目:
题目分析:
- 根据题意，树结构相同且节点值相同的两棵树为相同的树当所有节点的结构都相同时，树的结构就相同。那么，什么叫节点的结构相同呢？两节点的结构相同 ，也就是两个节点左子树的结构相同，右子树的结构也相同，因此，我们只需遍历两棵树，判断两棵树所有节点的结构是否相等以及所有节点的值是否相等，如果所有节点结构的结构和节点的值都相等，证明两棵树相同。
代码实现:
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
//递归时发现两节点均为空，则这两个节点结构相同
if(p == null && q == null) return true;
//两节点一个为空另一个不为空，则树结构不同
if(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的子树共有三种情况:(1). subroot与root是结构相同(2).subroot与root的左子树结构相同 (3).subroot与root的右子树结构相同如何判断两棵树结构相同呢？请看上一题(是的，两道题目判断两棵树相同的代码完全相同)如果两棵树结构不同，那么依次判断subroot是否与root的左子树结构相同，subroot是否与root的右子树结构相同即可。
以下是我第一次提交时的错误答案:
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//如果root与subRoot结构相同，返回true
if(isSameTree(root,subRoot)) return true;
//如果root的左子树与subRoot结构相同，返回true
if(isSameTree(root.left,subRoot)) return true;
//如果root的右子树与subRoot结构相同，返回true
if(isSameTree(root.right,subRoot)) return true;
走到这说明root,root的左子树，右子树均与subRoot不相同，返回false
return false;
}
//上一题的代码，判断两树结构相同
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) return true;
else if(p == null || q == null) return false;
else if(p.val != q.val) return false;
else return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
在思考后我发现，我只是对根节点进行了判断，并没有进行递归调用，也就是说，对于这个代码，如果subRoot与root，root的左子树和root的右子树都不相同，程序会直接返回false，这显然是错的
最终，我对代码进行了改进，增加了两节点分别为空时的判断条件，并在方法的调用上实现了递归调用，正确的代码如下:
class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
//subRoot为空时，subRoot一定是root的子树
if(subRoot == null) return true;
//subRoot不为空且root为空时，subRoot一定不是root的子树
if(root == null) return false;
//判断root与SubRoot是否相同
if(isSameTree(root,subRoot)) return true;
//注意这里一定要用isSubtree而不是上面代码中的isSameTree，否则无法实现递归
//判断subRoot是否是root左子树的子树
if(isSubtree(root.left,subRoot)) return true;
//判断subRoot是否是root右子树的子树
if(isSubtree(root.right,subRoot)) return true;
//这里说明subRoot不是root的子树，返回false
return false;
}
//这里用来判断两棵树是否相同，与上一题代码完全一致
private boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null) return true;
else if(p == null || q == null) return false;
else if(p.val != q.val) return false;
else return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
3.二叉树的最大深度
题目:
题目分析:
- 要求二叉树的最大深度，只需求出根节点左右子树的高度，并对更高的那颗子树的高度加1即可(加一是因为根节点深度为1)举例说明:示例中，根节点左子树高度为1，右子树高度为2，取更高的那颗子树的高度并加一，结果为 2+1 = 3.
代码实现:
class Solution {
public int maxDepth(TreeNode root) {
//节点为空时，返回0，也是递归的结束条件
if(root == null) return 0;
//递归调用maxDepth方法，每次递归比较左右子树的高度，并对更高的子树的高度+!
return Math.max(maxDepth(root.left) , maxDepth(root.right))+1;
}
}
4.平衡二叉树
题目:
题目分析:
- 题目给出了平衡二叉树的定义:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1因此，我们的做法是遍历整个二叉树，求得每个节点左右子树的高度并求得高度差的绝对值如何求每个节点左右子树的高度？请看上一题
注意:
并不是根节点平衡，这棵树就平衡了，一定要所有节点都平衡，这棵树才平衡，举例:
对于这棵树来说，根节点的左右子树是平衡的，但这棵树并不是一颗平衡二叉树，因为节点2是不平衡的，因此，判断平衡二叉树一定需要所有节点都平衡
初步实现代码:
//判断是不是平衡二叉树，需要判断这棵树所有节点的左右子树高度差是否小于等于1
//做法:遍历二叉树所有节点，判断当前节点是否平衡，不平衡就false
//如果当前节点平衡，继续判断当前节点的孩子节点是否平衡
//节点为空时，返回true
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
int leftHeight = height(root.left);
int rightHeight = height(root.right);
if(Math.abs(leftHeight - rightHeight)>1) return false;
//走到这里说明当前节点的左右子树平衡，继续递归判断其他节点
return isBalanced(root.left) && isBalanced(root.right) && Math.abs(leftHeight - rightHeight)<=1;
}
//求二叉树的高度
private int height(TreeNode root){
if(root == null) return 0;
return Math.max(height(root.left),height(root.right)) +1;
}
}
从正确性上来说，这个代码并没有问题，LeetCode中的测试用例也均可以通过，但是，通过观察可以发现，这个代码在判断当前节点是否平衡时进行了大量的重复运算，在计算节点的高度时，每求一次节点的高度，都需要从叶子结点依次往上+1，这样运算使得代码的执行效率非常低，那有没有更高效的方法呢？
更高效的方法的核心思路就是，判断高度时如果发现了子树中存在不平衡的节点，直接退出并返回false即可
改进后的代码如下:
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
//返回-1指求高度时某个孩子节点的子树不平衡
if(height(root) == -1) return false;
//走到这说明左右子树中不存在不平衡的节点
return true;//这里我一开始写的是return isBalanced(root.left) && isBalanced(root.right);
//但考虑到上面的height(root)走完没有返回-1，这说明所有节点都是平衡的，没有必要再判断左右子树浪费时间了
}
//求当前节点深度并判断当前节点左右子树的所有节点是否平衡
public int height(TreeNode root){
if(root == null) return 0;
int leftHeight = height(root.left);
int rightHeight = height(root.right);
//如果当前节点是平衡的，返回当前节点的深度
//注意:这里左右节点深度需要大于等于0是因为:如果上面求高度时如果返回-1可以直接捕获到
if(leftHeight>=0 && rightHeight >=0 && Math.abs(leftHeight - rightHeight) <=1)
return (leftHeight>rightHeight?leftHeight:rightHeight) + 1;
//当前节点不平衡，则返回-1(节点平衡时的返回值不可能为-1)
else
return -1;
}
}
5.对称二叉树
题目:
题目分析:
- 判断一颗二叉树是否为对称二叉树，只需判断该二叉树根节点的左右子树是否对称即可。重新编写一个方法，参数为左子树的根节点和右子树的根节点，判断左子树的右孩子节点和右子树的左孩子节点是否相等即可(节点为空和值相等均可看做相等)
代码实现:
class Solution {
public boolean isSymmetric(TreeNode root) {
//要判断的树为空树或只有一个根节点时，该树是轴对称的
if(root == null || root.left == null && root.right == null) return true;
//当根节点的左右子树一个为空一个不为空时，该树一定不是轴对称的
if(root.left == null || root.right == null) return false;
//判断根节点的左右子树是否对称
return isSymetricTree(root.left,root.right);
}
//判断左右子树是否对称
public boolean isSymetricTree(TreeNode leftTree,TreeNode rightTree){
//两节点均为空，对称
if(leftTree == null && rightTree == null) return true;
//一个节点为空一个节点不为空，一定不对称
if(leftTree == null || rightTree == null) return false;
//两节点不为空但值不相等时，一定不对称
if(leftTree.val != rightTree.val) return false;
//走到这里说明两节点对称，则继续判断这两个节点的左右子树是否对称
return isSymetricTree(leftTree.left,rightTree.right) && isSymetricTree(leftTree.right,rightTree.left);
}
}
未完待续…
