Leetcode 236 二叉树最近公共祖先

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

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

【Leetcode 236 二叉树最近公共祖先】示例 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 节点确定了一棵二叉树,pq 是这这棵二叉树上的两个节点,让你返回 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、得到函数的递归结果,你应该干什么?
与动态规划的思路类似,也是要明确「定义」「状态」「选择」
1) 这个函数是干嘛的?
描述一下 lowestCommonAncestor 这个函数的「定义」吧。
描述:给该函数输入三个参数 rootpq,它会返回一个节点。
情况 1,如果 pq 都在以 root 为根的树中,函数返回的即 pq 的最近公共祖先节点。
情况 2,如果 pq 都不在以 root 为根的树中,则理所当然地返回 null 呗。
情况 3,如果 pq 只有一个存在于 root 为根的树中,函数就返回那个节点。
题目说了输入的 pq 一定存在于以 root 为根的树中,但是递归过程中,以上三种情况都有可能发生,所以说这里要定义清楚,后续这些定义都会在代码中体现
2) 这个函数的参数中,变量是什么?
你描述一下这个函数的「状态」吧。
描述:函数参数中的变量是 root,因为根据框架,lowestCommonAncestor(root) 会递归调用 root.leftroot.right;至于 pq,我们要求它俩的公共祖先,它俩肯定不会变化的,就是在递归过程中一层一层透传下去。
你也可以理解这是「状态转移」,每次递归在做什么?不就是在把「以root为根」转移成「以root的子节点为根」,不断缩小问题规模嘛
3) 得到函数的递归结果,你该干嘛?
得到递归调用的结果后,你做什么「选择」?
先想 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); }

现在用递归调用的结果 leftright 来搞点事情。根据刚才第一个问题中对函数的定义,我们继续分情况讨论:
情况 1,如果 pq 都在以 root 为根的树中,那么 leftright 一定分别是 pq(从 base case 看出来的)。
情况 2,如果 pq 都不在以 root 为根的树中,直接返回 null
情况 3,如果 pq 只有一个存在于 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,你肯定有疑问,leftright 非空,分别是 pq,可以说明 root 是它们的公共祖先,但能确定 root 就是「最近」公共祖先吗?
这就是一个巧妙的地方了,因为这里是二叉树的后序遍历啊! 前序遍历可以理解为是从上往下,而后序遍历是从下往上,就好比从 pq 出发往上走,第一次相交的节点就是这个 root,你说这是不是最近公共祖先呢?

    推荐阅读