关于算法:Leetcode-236-二叉树最近公共祖先

7次阅读

共计 2348 个字符，预计需要花费 6 分钟才能阅读完成。

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

示例 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

首先这道题的函数签名如下：

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q);

root 节点确定了一棵二叉树，p 和 q 是这这棵二叉树上的两个节点，让你返回 p 节点和 q 节点的最近公共先人节点。

所有二叉树的套路都是一样的，能够先把遍历的框架写进去：

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 前序遍历
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    // 中序遍历
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    // 后序遍历
}

当初咱们思考如何增加一些细节，把框架革新成解法。遇到任何递归型的问题，无非就是灵魂三问：

1、这个函数是干嘛的？

2、这个函数参数中的变量是什么？

3、失去函数的递归后果，你应该干什么？

与动静布局的思路相似，也是要明确「定义」「状态」「抉择」

形容一下 lowestCommonAncestor 这个函数的「定义」吧。

形容：给该函数输出三个参数 root，p，q，它会返回一个节点。

状况 1，如果 p 和 q 都在以 root 为根的树中，函数返回的即 p 和 q 的最近公共先人节点。

状况 2，如果 p 和 q 都不在以 root 为根的树中，则天经地义地返回 null 呗。

状况 3，如果 p 和 q 只有一个存在于 root 为根的树中，函数就返回那个节点。

题目说了输出的 p 和 q 肯定存在于以 root 为根的树中，然而递归过程中，以上三种状况都有可能产生，所以说这里要定义分明，后续这些定义都会在代码中体现

你形容一下这个函数的「状态」吧。

形容：函数参数中的变量是 root，因为依据框架，lowestCommonAncestor(root) 会递归调用 root.left 和 root.right；至于 p 和 q，咱们要求它俩的公共先人，它俩必定不会变动的，就是在递归过程中一层一层透传下去。

你也能够了解这是「状态转移」，每次递归在做什么？不就是在把「以 root 为根」转移成「以 root 的子节点为根」，一直放大问题规模嘛

失去递归调用的后果后，你做什么「抉择」？

先想 base case，如果 root 为空，必定得返回 null。如果 root 自身就是 p 或者 q，比如说 root 就是 p 节点吧，如果 q 存在于以 root 为根的树中，显然 root 就是最近公共先人；即便 q 不存在于以 root 为根的树中，依照状况 3 的定义，也应该返回 root 节点。

以上两种状况的 base case 就能够把框架代码填充一点了：

TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    // 如果 root 为空
    if (root == null) return null;
    // 如果 root 自身就是 p 或者 q
    if (root == p || root == q) return root;

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

当初用递归调用的后果 left 和 right 来搞点事件。依据方才第一个问题中对函数的定义，咱们持续分状况探讨：

状况 1，如果 p 和 q 都在以 root 为根的树中，那么 left 和 right 肯定别离是 p 和 q（从 base case 看进去的）。

状况 2，如果 p 和 q 都不在以 root 为根的树中，间接返回 null。

状况 3，如果 p 和 q 只有一个存在于 root 为根的树中，函数返回该节点。

明确了下面三点，能够间接看解法代码了：

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

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 状况 1
        if (left != null && right !=  null) {return root;}
        // 状况 2
        if (left == null && right == null) {return null;}
        // 状况 3
        return left == null ? right : left;
    }
}

对于状况 1，你必定有疑难，left 和 right 非空，别离是 p 和 q，能够阐明 root 是它们的公共先人，但能确定 root 就是「最近」公共先人吗？

这就是一个奇妙的中央了， 因为这里是二叉树的后序遍历啊！ 前序遍历能够了解为是从上往下，而后序遍历是从下往上，就好比从 p 和 q 登程往上走，第一次相交的节点就是这个 root，你说这是不是最近公共先人呢？

正文完