二叉树常见题记录

二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：给定二叉树 [3,9,20,null,null,15,7]

返回它的最大深度 3

这题就像斐波那契数列那样往一个方向延展的递归

public static void main(String[] args) {
    TreeNode root = new TreeNode(1,
            new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
    System.out.println(maxDepth(root));
}

public static int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
}

对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

public static void main(String[] args) {
    TreeNode root = new TreeNode(1,
            new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
    System.out.println(isSymmetric(root));
}

public static boolean isSymmetric(TreeNode root) {
    return isMirror(root.left, root.right);
}

public static boolean isMirror(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return true;
    // 既然有且至少一个不为 null，说明只要一个为 null 那一定是不同的（要么就都不为 null）
    if (t1 == null || t2 == null) return false;
    return (t1.val == t2.val)
            && isMirror(t1.left, t2.right)
            && isMirror(t1.right, t2.left);
}

路径总和

参考资料蓝士钦的回答

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。

叶子节点是指没有子节点的节点。

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true

树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

思路：

递归法，每递归到一个节点，就拿 target 减去当前节点值，如果最后一个叶子节点等于 target 剩下的值，则存在路径总和等于 target。

反之如果递归到叶子节点后，剩余的 target 值不等于叶子节点，说明不存在路径总和等于 target。

public static void main(String[] args) {
    TreeNode root = new TreeNode(1,
            new TreeNode(2, new TreeNode(4), new TreeNode(5)),
            new TreeNode(3));
    System.out.println(hasPathSum(root, 8));
}

public static boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;

    if (root.left == null && root.right == null) {
        return root.val == targetSum;
    }

    // 只要一个返回 true 就存在
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}

二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

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

提示：

树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同。
p != q
p 和 q 均存在于给定的二叉树中。

题解递归解析：

参考资料 236. 二叉树的最近公共祖先（后序遍历 DFS ，清晰图解）

祖先的定义：若节点 p 在节点 root 的左（右）子树中，或 p = root，则称 root 是 p 的祖先。

最近公共祖先的定义：设节点 root 为节点 p, q 的某公共祖先，若其左子节点 root.left 和右子节点 root.right 都不是 p, q 的公共祖先，则称 root 是 “最近的公共祖先” 。

根据以上定义，若 root 是 p, q 的最近公共祖先，则只可能为以下情况之一：

p 和 q 在 root 的子树中，且分列 root 的异侧（即分别在左、右子树中）；
p = root，且 q 在 root 的左或右子树中；
q = root，且 p 在 root 的左或右子树中；

考虑通过递归对二叉树进行后序遍历，当遇到节点 p 或 q 时返回。从底至顶回溯，当节点 p, q 在节点 root 的异侧时，节点 root 即为最近公共祖先，则向上返回 root。

递归解析：

终止条件：

当越过叶节点，则直接返回 null；
当 root 等于 p, q，则直接返回 root；

递推工作：

开启递归左子节点，返回值记为 left
开启递归右子节点，返回值记为 right

返回值：

根据 left 和 right，可展开为四种情况；

1、当 left 和 right 同时为空：说明 root 的左 / 右子树中都不包含 p,q，返回 null；

2、当 left 和 right 同时不为空：说明 p,q 分列在 root 的异侧（分别在左 / 右子树），因此 root 为最近公共祖先，返回 root；

3、当 left 为空，right 不为空：p,q 都不在 root 的左子树中，直接返回 right 。具体可分为两种情况：

p,q 其中一个在 root 的右子树中，此时 right 指向 p（假设为 p）；
p,q 两节点都在 root 的右子树中，此时的 right 指向最近公共祖先节点；

4、当 right 为空，left 不为空，同上

代码示例：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        if(left == null && right == null) return null; // 1.
        if(left == null) return right; // 3.
        if(right == null) return left; // 4.

        return root; // 2. if(left != null and right != null)
    }
}

判断是否是平衡二叉树

首先平衡二叉树的定义：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

最直接的做法，遍历每个结点，借助一个获取树深度的递归函数，根据该结点的左右子树高度差判断是否平衡，然后递归地对左右子树进行判断。

public classSolution {
    public boolean IsBalanced_Solution(TreeNode root) {
        if(root == null) {
            return true;
        }
        return Math.abs(maxDepth(root.left) - maxDepth(root.right)) <= 1 &&
            IsBalanced_Solution(root.left) && 
            IsBalanced_Solution(root.right);
    }
     
    private int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }
}

这种做法有很明显的问题，在判断上层结点的时候，会多次重复遍历下层结点，增加了不必要的开销。

如果改为从下往上遍历，如果子树是平衡二叉树，则返回子树的高度；如果发现子树不是平衡二叉树，则直接停止遍历，这样至多只对每个结点访问一次。

public class Solution {
    public boolean IsBalanced_Solution(TreeNode root) {
        return getDepth(root) != -1;
    }
    
    private int getDepth(TreeNode root) {
        if (root == null) return 0;

        int left = getDepth(root.left);
        if (left == -1) return -1;

        int right = getDepth(root.right);
        if (right == -1) return -1;

        return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
    }
}

二叉树的最大深度​

对称二叉树​

路径总和​

二叉树的最近公共祖先​

题解 递归解析：​

判断是否是平衡二叉树​