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

链接：235.二叉搜索树的最近公共祖先
难度：Medium
标签：树、深度优先搜索、二叉搜索树、二叉树
简介：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

题解 1 - java

• 编辑时间：2020-02-24
• 执行用时：6ms
• 内存消耗：41.9MB
• 编程语言：java
• 解法介绍：二分判断如果值在两边则当前点就为公共祖先。

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

题解 2 - javascript

• 编辑时间：2020-09-27
• 执行用时：112ms
• 内存消耗：47.2MB
• 编程语言：javascript
• 解法介绍：根据二叉搜索树的特性进行递归。

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
  const val = root.val;
  const pVal = p.val;
  const qVal = q.val;
  if ((val < pVal && val > qVal) || (val > pVal && val < qVal) || val === pVal || val === qVal)
    return root;
  if (val < pVal && val < qVal) return lowestCommonAncestor(root.right, p, q);
  if (val > pVal && val > qVal) return lowestCommonAncestor(root.left, p, q);
};

题解 3 - python

• 编辑时间：2024-02-25
• 执行用时：53ms
• 内存消耗：19.96MB
• 编程语言：python
• 解法介绍：通过bst特性进行左右区分。

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