Lowest Common Ancestor of a Binary Search Tree-K6K4.com

原题： https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

题意： 给定一棵二叉搜索树（BST），寻找BST中两个给定节点的最近公共祖先（LCA）。

根据维基百科对LCA的定义：“节点v与w的最近公共祖先是树T上同时拥有v与w作为后继的最低节点（我们允许将一个节点当做其本身的后继）”

例子：

给定BST如下：
        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5
节点2和8的最近公共祖先（LCA）是6，节点2和4的LCA是2，因为根据LCA的定义，一个节点可以是其本身的后继。

标签： lca、bst、祖先、后继、lowest、面试

猜你感兴趣的圈子：

LeetCode交流圈

Bingo

2017-08-18 17:01:49 1楼#1层

Python：迭代法

class Solution:
    # @param {TreeNode} root
    # @param {TreeNode} p
    # @param {TreeNode} q
    # @return {TreeNode}
    def lowestCommonAncestor(self, root, p, q):
        while (p.val - root.val) * (q.val - root.val) > 0:
            root = [root.left, root.right][p.val > root.val]
        return root

Bingo

2017-08-18 17:02:14 2楼#1层

Python：递归法

class Solution:
    # @param {TreeNode} root
    # @param {TreeNode} p
    # @param {TreeNode} q
    # @return {TreeNode}
    def lowestCommonAncestor(self, root, p, q):
        if (p.val - root.val) * (q.val - root.val) <= 0:
            return root
        elif p.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        else:
            return self.lowestCommonAncestor(root.right, p, q)

Bingo

2017-08-18 17:03:29 3楼#1层

Java：迭代法

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    while ((root.val - p.val) * (root.val - q.val) > 0)
        root = p.val < root.val ? root.left : root.right;
    return root;
}

Bingo

2017-08-18 17:03:55 4楼#1层

Java：递归法

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    return (root.val - p.val) * (root.val - q.val) < 1 ? root :
           lowestCommonAncestor(p.val < root.val ? root.left : root.right, p, q);
}

Bingo

2017-08-18 17:04:31 5楼#1层

C++：迭代法

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

Bingo

2017-08-18 17:04:50 6楼#1层

C++：递归法

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

取消

回复

推荐圈子

LeetCode交流圈