题目描述

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

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

题目示例

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

解题思路

考虑通过递归对二叉树进行先序遍历，当遇到节点 p 或 q 时返回。从底至顶回溯，当节点 p,q 在节点 root 的异侧时，节点 root 即为最近公共祖先，则向上返回 root 。

终止条件：

• 当越过叶节点，直接返回 null；
• 当 root 等于 p 或者 q，直接返回 root；

递归工作：

• 开启递归左子节点，记录为 left，左子树的最大祖先；
• 开启递归右子节点，记录为 right，右子树的最大祖先；

返回值：根据 left 和 right，可分为四种情况

• 当 left 和 right 同时为空，说明左右子树都不包含 p/q，直接返回 null；
• 当 left 和 right 同时不为空，说明 p 和 q 分别在左子树和右子树中，因此 root 为最近公共祖先，返回 root；
• 当 left 为空，但 right 不为空，说明 p/q 不在左子树上，直接返回 right；
• 当 right 为空，但 left 不为空，说明 p/q 不在右子树上，直接返回 left。

参考代码

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) {
            return right;
        }
        if(right == null) {
            return left;
        }
        return root;
    }
}