2022.3.16 LeetCode —— 二叉树

一、今日刷题

1. 第七部分：二叉树 -- 236. 二叉树的最近公共祖先

跳转LeetCode

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

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

答案代码：

开始并没有什么思路，题解将本题分成了三种情况：

情况 1，如果 p 和 q 都在以 root 为根的树中，函数返回的即使 p 和 q 的最近公共祖先节点。
情况 2，那如果 p 和 q 都不在以 root 为根的树中怎么办呢？函数理所当然地返回 null 呗。
情况 3，那如果 p 和 q 只有一个存在于 root 为根的树中呢？函数就会返回那个节点。

分情况讨论：

情况 1，如果 p 和 q 都在以 root 为根的树中，那么 left 和 right 一定分别是 p 和 q（从 base case 看出来的）。
情况 2，如果 p 和 q 都不在以 root 为根的树中，直接返回 null。
情况 3，如果 p 和 q 只有一个存在于 root 为根的树中，函数返回该节点。

代码是如何遍历树的并不好理解，以下图为例，找 9 & 11的最近公共祖先：

遍历到节点的顺序为：1 - 2 - 4 - 8 - 9 - 4 - 5 - 10 - 11 - 5 - 2

因为我们是自底向上从叶子节点开始更新的，所以在所有满足条件的公共祖先中一定是深度最大的祖先先被访问到。

package BinaryTree.BinarSearchTree;


public class LowestCommonAncestor {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)), new TreeNode(6));
        LowestCommonAncestor ancestor = new LowestCommonAncestor();
        TreeNode ans = ancestor.lowestCommonAncestor(root, new TreeNode(1), new TreeNode(3));
        System.out.println(ans);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        //一旦自底向上找到了 p、q 节点，就将函数逐层返回
        if (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 root;
        }
        if (left == null && right == null) {
            return null;
        }
        return left == null ? right : left;
    }
}