Cocolib

Appearance

On this page

二叉搜索树的最近公共祖先 ​

Question

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

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

思路 ​

那么本题是二叉搜索树，二叉搜索树是有序的，那得好好利用一下这个特点。

在有序树里，如果判断一个节点的左子树里有p，右子树里有q呢？

因为是有序树，所有 如果 中间节点是 q 和 p 的公共祖先，那么 中节点的数组 一定是在 [p, q]区间的。即 中节点 > p && 中节点 < q 或者 中节点 > q && 中节点 < p。

当我们从上向下去递归遍历，第一次遇到 cur节点是数值在 [p, q] 区间中，那么cur就是 p和q的最近公共祖先。

理解这一点，本题就很好解了。

js
var lowestCommonAncestor = function(root, p, q) {
    if(root===null) return root
    if(root.val===p.val) return root
    if(root.val===q.val) return root
    if(root.val>p.val&&root.val<q.val)  return root
    //单层逻辑
    if(root.val<q.val)
        return lowestCommonAncestor(root.right, p, q)
    if(root.val>p.val)
        return lowestCommonAncestor(root.left, p, q)
    return root
};