二叉树的最近公共祖先
2020-10-04 本文已影响0人
超帅牛蛙
该题来自 leetcode 236， https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
题目
给定一个二叉树, 找到该树中两个指定节点 p、q 的最近公共祖先。
分析
首先设 p、q 的最近公共祖先为 root。这个题目最关键的地方在于理解以下两点：
- 要么 p，q 两个节点只在 root 的一个子树上，此时 root 必然就是 p、q 中深度小的那个，即 root == p || root == q
- 要么 p，q 两个节点分别在 root 的两个子树上
下面先来证明第一点：
p，q 两个节点只在最近公共祖先 root 的一个子树上，此时 root 必然就是 p、q 中深度小的那个，即 root == p || root == q
使用反证法。
假设 p，q 两个节点只在最近公共祖先 root 的一个子树上，且 root != p && root != q，如下图：
很明显，此时 p、q 的最近公共祖先为 root'，而非 root。并且 p、q 也分别 root' 的两个子树上。这与 root 是最近公共祖先，以及，p、q 同在 root' 的一个子树上的假设矛盾。
第二点则非常容易理解，如果 p、q 不同在 root 的一个子树上，则必然分别在两个子树上。
理解了这两点有什么用呢？
这两点可以有下面的推论：
- 假设 root 为 p、q 的任一公共父节点，如果 p 、q 分别在 root 的左右子树上，则 root 必为 p、q 最近公共祖先。（可由上述第一点反证推出）
- 对于 p、q 的所有公共父节点， 如果 p、q 均不分别在其左右子树，而是同在其一颗子树上，则 p、q 的最近公共节点一定是 p、q 中深度较小的那个。
有了上面这两点，就可以写出非常简洁的递归代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
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); // 如果 left != null，则 p 或 q 在 root 的左子树中
TreeNode right = lowestCommonAncestor(root.right, p, q); // // 如果 right != null，则 p 或 q 在 root 的右子树中
if (left != null && right != null) return root; // 如果 left != null && right!= null，则对应推论第一点
return left != null ? left : right; // 在遍历完所有可能的父节点后，p、q 均不分在父节点的左右两侧，对应推论第二点
}
}
