树形结构（4）（Java语言）——二叉树（3）

二叉树相关的OJ题

第一题

题目

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例2：

输入：p = [1,2], q = [1,null,2]
输出：false

示例3：

输入：p = [1,2,1], q = [1,1,2]
输出：false

代码

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

解题思路

这个问题是比较简单的，我们只需要把情况考虑完全，这个问题就轻而易举的解决了。首先什么是两棵完全的二叉树，第一，节点的值相同；第二，树的结构相同。那么为了比较树的各个节点，我们就需要遍历整颗树。在遍历过程中我们就会遇到这几种情况：

1. 当任意一棵树的节点为null时，另一棵树不为null，那么两棵树不一样。
2. 当两棵树都为null时，两棵树一样。
3. 当两棵树的节点都不为null，但是对应的val值不一样，那么两棵树不一样。
4. 节点既不为null且对应值相等，那么继续向节点的左右孩子遍历。

知道了这4种情况，情况我们解决这个问题就很方便了，首先判断上面的3种情况，如果都不满足，那么就用递归往下遍历，最后返回对应两个节点的左右孩子节点的情况。
题目链接： LeetCode——100.相同的树

第二道题

题目

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
示例1：

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

示例2：

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

代码

class Solution {
    private boolean isSameTree(TreeNode p,TreeNode q){
        if((p == null && q != null) || (p != null && q ==null)){
            return false;
        }
        if(p == null && q == null){
            return true;
        }
        if(p.val != q.val){
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null && subRoot ==null){
            return true;
        }
        if(root == null){
            return false;
        }
        //根节点和subRoot是不是两棵相同的树
        if(isSameTree(root,subRoot)){
            return true;
        }
        if(isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }
}

题目解析

这道题我们在上一道题的基础之上解决，举个例子：

同样的，我们会遇到一下几种情况：

1. root树和subRoot树都为空树，返回true。
2. root树为空树，但是subRoot不为空树，返回false。
3. 在两棵树都不为空树的情况下，这两棵树相同，返回true。
4. 上述情况都不满足，比较subRoot是否是root左右子树的子树。
5. 最后4种情况都不满足，返回false。

按照这个步骤，我们需要借助第一题的方法，解决这道题目就很简单了。
题目链接 LeetCode——572.另一棵树的子树

第三道题

题目

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明： 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]

返回它的最大深度3。

代码

public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);
        return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
    }

题目解析

这条题目我们在上一篇博客中介绍过，我们可以采用子问题的方法来解决，举个例子：

如果一棵树为null时，返回0。接着采用递归的方法，想要求根为“3”的树的高度，可以求“3”的左右子树根为“9”的树的高度和根为“20”的高度的最大值再加1（加1的目的在于“3”本身的高度），同理求根为“20”的左右子树的高度的最大值再加上1，最后得到树的高度。
题目链接：LeetCode——104.二叉树的最大深度

第四题

题目

给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例3：

输入：root = []
输出：true

代码

/**
 1. Definition for a binary tree node.
 2. public class TreeNode {
 3.     int val;
 4.     TreeNode left;
 5.     TreeNode right;
 6.     TreeNode() {}
 7.     TreeNode(int val) { this.val = val; }
 8.     TreeNode(int val, TreeNode left, TreeNode right) {
 9.         this.val = val;
 10.         this.left = left;
 11.         this.right = right;
 12.     }
 13. }
 */
class Solution {
    public int height(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftheight = height(root.left) + 1;
        int rightheight = height(root.right) + 1;
        return leftheight > rightheight ? leftheight : rightheight;
    }

    public boolean isBalanced(TreeNode root) {
        if(root == null){
            return true;
        }
        int leftheight = height(root.left);
        int rightheight = height(root.right);
        return Math.abs(leftheight - rightheight) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
}

题目解析

这条题目可以在求树的高度的基础上完成，我们知道满足平衡二叉树有三个条件：

1.以root节点的树是平衡的
2.root的左子树是平衡的
3.root的右子树是平衡的

也就是说我们可以求出root节点左子树的高度和root节点右子树的高度，他们之间的差值要小于等于1，并且左子树和右子树也要满足。
题目链接：判断一颗二叉树是否是平衡二叉树。

第五题

题目

给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例2：

输入：root = [1,2,2,null,3,null,3]
输出：false

代码

/**
 * 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 {

    public boolean isSymmetricHelper(TreeNode left,TreeNode right){
        if(left == null && right == null){
            return true;
        }
        if((left == null && right != null) || (left != null && right == null) || left.val != right.val){
            return false;
        }
        return isSymmetricHelper(left.left,right.right) && isSymmetricHelper(left.right,right.left);
    }

    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return isSymmetricHelper(root.left,root.right);
    }
}

解题思路

这道问题其实不难，首先我们通过判断一棵树是否是空树（排除特殊情况），然后再判断左右子树是否为对称的，有四种情况：

1.左子树为空，右子树不为空，返回false
2.右子树为空，左子树不为空，返回false
3.左子树和右子树都不为空，但是他们的值不相等，返回false
4.左子树右子树都为空，返回ture

代码中我将1，2，3用一个if条件完成，最后用递归的方式返回节点的左右子树的结果。