【Leetcode 热题 100】236. 二叉树的最近公共祖先

问题背景

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：对于有根树 $T$ 的两个节点 $p$、$q$，最近公共祖先表示为一个节点 $x$，满足 $x$ 是 $p$、$q$ 的祖先且 $x$ 的深度尽可能大（一个节点也可以是它自己的祖先）。

数据约束

• 树中节点数目在范围 $[2,10^5]$ 内。
• $-10^9\le Node.val\le 10^9$
• 所有 $Node.val$ 互不相同 。
• $p\le 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);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 在左子树或者右子树中都找到了相应的节点，那么就把当前节点向上返回
        if(left != null && right != null) {
            return root;
        }
        // 返回递归子树时得到的非空的结果，两者都为空时随便返回哪个都可以，合并到 right 中
        return left != null ? left : right;
    }
}