图解LeetCode——剑指 Offer 68 - II. 二叉树的最近公共祖先

一、题目

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

百科中最近公共祖先的定义为：

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

二、示例

2.1> 示例 1:

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

2.2> 示例 2:

【输入】 root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 【输出】 5 【解释】 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

说明：

• • 所有节点的值都是唯一的。
• • p、q 为不同节点且均存在于给定的二叉树中。

三、解题思路

根据题目描述，会给我们两个节点，分别是TreeNode p和TreeNode q，然后我们需要在一个二叉树中去寻找着两个给定节点的最近公共祖先。这个题与《剑指 Offer 68 - I. 二叉搜索树的最近公共祖先》很类似，只不过我们这个树是普通的二叉树，不能利用二叉搜索树的特性来解题了。

那么我们知道，针对某一个节点来说，它是具有左子树和右子树这两个属性的，那么对于随机给出的p节点和q节点来说，就会有如下3种情况，请见下图所示：

根据上图描述，我们可以得出如下3种情况：

【情况1】当p节点和q节点分别在根节点的左子树和右子树中时，那么根节点就是最近公共祖先节点。 【情况2】当p节点和q节点都在根节点的左子树中时，第一个遍历到的节点就是最近公共祖先节点。 【情况3】当p节点和q节点都在根节点的右子树中时，第一个遍历到的节点就是最近公共祖先节点。

所以，针对上面的分析，我们可以通过深度遍历来遍历二叉树中的节点，当发现某个节点等于p节点或者等于q节点，则终止这一侧子树的遍历。然后当根节点的左子树和右子树都遍历完毕后，再根据以上3种情况，返回这道题的最终结果即可。

解题思路我们说完了，下面还是按照惯例，以输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 8为例，看一下具体处理流程是怎么样子的。请见下图所示：

四、代码实现

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return null;
        TreeNode ln = lowestCommonAncestor(root.left, p, q);
        TreeNode rn = lowestCommonAncestor(root.right, p, q);
        return (ln != null && rn != null) ? root : (ln != null ? ln : rn);
    }
}