参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

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

力扣题目链接

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

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

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

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

示例 2:

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

说明:

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

算法公开课

《代码随想录》算法视频公开课：二叉搜索树找祖先就有点不一样了！| 235. 二叉搜索树的最近公共祖先，相信结合视频在看本篇题解，更有助于大家对本题的理解。

思路

做过二叉树：公共祖先问题题目的同学应该知道，利用回溯从底向上搜索，遇到一个节点的左子树里有p，右子树里有q，那么当前节点就是最近公共祖先。

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

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

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

那么只要从上到下去遍历，遇到 cur节点是数值在[p, q]区间中则一定可以说明该节点cur就是q 和 p的公共祖先。那问题来了，一定是最近公共祖先吗？

如图，我们从根节点搜索，第一次遇到 cur节点是数值在[p, q]区间中，即节点5，此时可以说明 p 和 q 一定分别存在于节点 5的左子树，和右子树中。

此时节点5是不是最近公共祖先？如果从节点5继续向左遍历，那么将错过成为q的祖先，如果从节点5继续向右遍历则错过成为p的祖先。

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

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

而递归遍历顺序，本题就不涉及到前中后序了（这里没有中节点的处理逻辑，遍历顺序无所谓了）。

如图所示：p为节点6，q为节点9

可以看出直接按照指定的方向，就可以找到节点8，为最近公共祖先，而且不需要遍历整棵树，找到结果直接返回！

递归法

递归三部曲如下：

确定递归函数返回值以及参数

参数就是当前节点，以及两个结点 p、q。

返回值是要返回最近公共祖先，所以是TreeNode * 。

代码如下：

TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q)

确定终止条件

遇到空返回就可以了，代码如下：

if (cur == NULL) return cur;

其实都不需要这个终止条件，因为题目中说了p、q 为不同节点且均存在于给定的二叉搜索树中。也就是说一定会找到公共祖先的，所以并不存在遇到空的情况。

确定单层递归的逻辑

在遍历二叉搜索树的时候就是寻找区间[p->val, q->val]（注意这里是左闭又闭）

那么如果 cur->val 大于 p->val，同时 cur->val 大于q->val，那么就应该向左遍历（说明目标区间在左子树上）。

需要注意的是此时不知道p和q谁大，所以两个都要判断

代码如下：

if (cur->val > p->val && cur->val > q->val) {
    TreeNode* left = traversal(cur->left, p, q);
    if (left != NULL) {
        return left;
    }
}

细心的同学会发现，在这里调用递归函数的地方，把递归函数的返回值left，直接return。

在二叉树：公共祖先问题中，如果递归函数有返回值，如何区分要搜索一条边，还是搜索整个树。

搜索一条边的写法：

if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;

搜索整个树写法：

left = 递归函数(root->left);
right = 递归函数(root->right);
left与right的逻辑处理;

本题就是标准的搜索一条边的写法，遇到递归函数的返回值，如果不为空，立刻返回。

如果 cur->val 小于 p->val，同时 cur->val 小于 q->val，那么就应该向右遍历（目标区间在右子树）。

if (cur->val < p->val && cur->val < q->val) {
    TreeNode* right = traversal(cur->right, p, q);
    if (right != NULL) {
        return right;
    }
}

剩下的情况，就是cur节点在区间（p->val <= cur->val && cur->val <= q->val）或者（q->val <= cur->val && cur->val <= p->val）中，那么cur就是最近公共祖先了，直接返回cur。

代码如下：

return cur;

那么整体递归代码如下:

class Solution {
private:
    TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {
        if (cur == NULL) return cur;
                                                        // 中
        if (cur->val > p->val && cur->val > q->val) {   // 左
            TreeNode* left = traversal(cur->left, p, q);
            if (left != NULL) {
                return left;
            }
        }

        if (cur->val < p->val && cur->val < q->val) {   // 右
            TreeNode* right = traversal(cur->right, p, q);
            if (right != NULL) {
                return right;
            }
        }
        return cur;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return traversal(root, p, q);
    }
};

精简后代码如下：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root->val > p->val && root->val > q->val) {
            return lowestCommonAncestor(root->left, p, q);
        } else if (root->val < p->val && root->val < q->val) {
            return lowestCommonAncestor(root->right, p, q);
        } else return root;
    }
};

迭代法

对于二叉搜索树的迭代法，大家应该在二叉树：二叉搜索树登场！就了解了。

利用其有序性，迭代的方式还是比较简单的，解题思路在递归中已经分析了。

迭代代码如下：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while(root) {
            if (root->val > p->val && root->val > q->val) {
                root = root->left;
            } else if (root->val < p->val && root->val < q->val) {
                root = root->right;
            } else return root;
        }
        return NULL;
    }
};

灵魂拷问：是不是又被简单的迭代法感动到痛哭流涕？

总结

对于二叉搜索树的最近祖先问题，其实要比普通二叉树公共祖先问题简单的多。

不用使用回溯，二叉搜索树自带方向性，可以方便的从上向下查找目标区间，遇到目标区间内的节点，直接返回。

最后给出了对应的迭代法，二叉搜索树的迭代法甚至比递归更容易理解，也是因为其有序性（自带方向性），按照目标区间找就行了。

其他语言版本

Java

递归法：

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

迭代法：

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

Python

递归法：

class Solution:
    """二叉搜索树的最近公共祖先 递归法"""

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        if root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        return root

迭代法：

class Solution:
    """二叉搜索树的最近公共祖先 迭代法"""

    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while True:
            if root.val > p.val and root.val > q.val:
                root = root.left
            elif root.val < p.val and root.val < q.val:
                root = root.right
            else:
                return root

Go

递归法：

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil {
        return nil
    }
    for {
         if root.Val > p.Val && root.Val > q.Val {
            root = root.Left
    }
        if root.Val < p.Val && root.Val < q.Val {
            root = root.Right
        }
        if (root.Val - p.Val) * (root.Val - q.Val) <= 0 {
            return root
        }
    }
        return root
}

JavaScript

递归法：

var lowestCommonAncestor = function(root, p, q) {
    // 使用递归的方法
    // 1. 使用给定的递归函数lowestCommonAncestor
    // 2. 确定递归终止条件
    if(root === null) {
        return root;
    }
    if(root.val > p.val && root.val > q.val) {
        // 向左子树查询
         return root.left = lowestCommonAncestor(root.left,p,q);
    }
    if(root.val < p.val && root.val < q.val) {
        // 向右子树查询
        return root.right = lowestCommonAncestor(root.right,p,q);
    }
    return root;
};

迭代法

var lowestCommonAncestor = function(root, p, q) {
    // 使用迭代的方法
    while(root) {
        if(root.val > p.val && root.val > q.val) {
            root = root.left;
        }else if(root.val < p.val && root.val < q.val) {
            root = root.right;
        }else {
            return root;
        }
        
    }
    return null;
};

TypeScript

递归法：

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
    if (root.val > p.val && root.val > q.val)
        return lowestCommonAncestor(root.left, p, q);
    if (root.val < p.val && root.val < q.val)
        return lowestCommonAncestor(root.right, p, q);
    return root;
};

迭代法：

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
    while (root !== null) {
        if (root.val > p.val && root.val > q.val) {
            root = root.left;
        } else if (root.val < p.val && root.val < q.val) {
            root = root.right;
        } else {
            return root;
        };
    };
    return null;
};

Scala

递归:

object Solution {
  def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode): TreeNode = {
    // scala中每个关键字都有其返回值，于是可以不写return
    if (root.value > p.value && root.value > q.value) lowestCommonAncestor(root.left, p, q)
    else if (root.value < p.value && root.value < q.value) lowestCommonAncestor(root.right, p, q)
    else root
  }
}

迭代:

object Solution {
  def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode): TreeNode = {
    var curNode = root  // 因为root是不可变量，所以要赋值给curNode一个可变量
    while(curNode != null){
      if(curNode.value > p.value && curNode.value > q.value) curNode = curNode.left
      else if(curNode.value < p.value && curNode.value < q.value) curNode = curNode.right
      else return curNode
    }
    null
  }
}

rust

递归：

impl Solution {
    pub fn lowest_common_ancestor(
        root: Option<Rc<RefCell<TreeNode>>>,
        p: Option<Rc<RefCell<TreeNode>>>,
        q: Option<Rc<RefCell<TreeNode>>>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        let q_val = q.as_ref().unwrap().borrow().val;
        let p_val = p.as_ref().unwrap().borrow().val;
        let root_val = root.as_ref().unwrap().borrow().val;

        if root_val > q_val && root_val > p_val {
            return Self::lowest_common_ancestor(
                root.as_ref().unwrap().borrow().left.clone(),
                p,
                q,
            );
        };

        if root_val < q_val && root_val < p_val {
            return Self::lowest_common_ancestor(
                root.as_ref().unwrap().borrow().right.clone(),
                p,
                q,
            );
        }
        root
    }
}

迭代：

impl Solution {
    pub fn lowest_common_ancestor(
        mut root: Option<Rc<RefCell<TreeNode>>>,
        p: Option<Rc<RefCell<TreeNode>>>,
        q: Option<Rc<RefCell<TreeNode>>>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        let p_val = p.unwrap().borrow().val;
        let q_val = q.unwrap().borrow().val;
        while let Some(node) = root.clone() {
            let root_val = node.borrow().val;
            if root_val > q_val && root_val > p_val {
                root = node.borrow().left.clone();
            } else if root_val < q_val && root_val < p_val {
                root = node.borrow().right.clone();
            } else {
                return root;
            }
        }
        None
    }
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

0235.二叉搜索树的最近公共祖先.md

0235.二叉搜索树的最近公共祖先.md

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

算法公开课

思路

递归法

迭代法

总结

其他语言版本

Java

Python

Go

JavaScript

TypeScript

Scala

rust

Files

0235.二叉搜索树的最近公共祖先.md

Latest commit

History

0235.二叉搜索树的最近公共祖先.md

File metadata and controls

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

算法公开课

思路

递归法

迭代法

总结

其他语言版本

Java

Python

Go

JavaScript

TypeScript

Scala

rust