图解LeetCode——剑指 Offer 68 – I. 二叉搜索树的最近公共祖先

一、题目

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

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

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

二、示例

2.1> 示例 1:

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

2.2> 示例 2:

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

说明：

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

三、解题思路

根据题目描述，我们给我们两个节点TreeNode p和TreeNode q，然后在二叉搜索树中去寻找最近公共祖先。那么题目中给出了非常关键的一个信息就是——二叉搜索树，那么这种二叉树具有如下的特征：

【若它的左子树不空】则左子树上所有结点的值均小于它的根结点的值；
【若它的右子树不空】则右子树上所有结点的值均大于它的根结点的值；

所以针对如上特点，我们可以根据TreeNode p和TreeNode q这两个树节点处于二叉搜索树不同位置来总结出如下的3种情况：

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

【情况1】当根节点的值处于p节点的值和q节点的值之间时，那么根节点就是最近公共祖先节点。
【情况2】当根节点的值大于p节点的值和q节点的值时，那么我们只需要遍历根节点的左子树，然后第一个遍历到的节点就是最近公共祖先节点。
【情况3】当根节点的值小于p节点的值和q节点的值时，那么我们只需要遍历根节点的右子树，然后第一个遍历到的节点就是最近公共祖先节点。
【注意】每当遍历到一个子树的根节点时，都需要对比上面的3种情况，来决定执行那块逻辑。

上面就是具体的解题思路了，下面我们以输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4为例，看一下具体的处理过程。请见下图所示：

四、代码实现

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root.val < p.val && root.val < q.val) 
            return lowestCommonAncestor(root.right, p, q);
        if (root.val > p.val && root.val > q.val) 
            return lowestCommonAncestor(root.left, p, q);
        return root;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o)/ ~ 「干货分享，每天更新」

© 著作权归作者所有,转载或内容合作请联系作者