LowestCommonAncestorOfABinarySearchTree [source code]

public class LowestCommonAncestorOfABinarySearchTree {
static
/******************************************************************************/
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        else if (root.val == p.val || root.val == q.val) return root;
        else if ((root.val - p.val) * (root.val - q.val) < 0) return root;
        else if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
        else return lowestCommonAncestor(root.left, p, q);
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        LowestCommonAncestorOfABinarySearchTree2.Solution tester = new LowestCommonAncestorOfABinarySearchTree2.Solution();
        TreeNode input1 = new TreeNode(2);
        input1.right = new TreeNode(3);
        TreeNode output1 = tester.lowestCommonAncestor(input1, new TreeNode(3), new TreeNode(2));
        // System.out.println(tester.contains(input1, new TreeNode(3)));   
        // System.out.println(tester.contains(input1, new TreeNode(2)));
        System.out.println(output1.val);
    }
}

如果是任意的一个 tree, 大概有意思思路, 需要用到两个 recursion, 就是第一个 recursion 走的过程中, 每走到一个 node, 就判断左右两个 child 是否contains需要搜索的两个 key, 如果两个 key 在同一个child 里面, 就继续朝那个 child 里面走; 如果两个 key 一人在一边, 或者两个 key 只有一个 key 是在一个 child 当中, 另一个 key 就是当前 node 的 val, 那么就当前 node 就是 LCA;

不过这个题目是 BST, 感觉有更简单的方法;

BST 首先一个默认的assumption 是没有 duplicate key, 这个可以适当的简化代码;

BST里面的搜索不是单纯的DFS, 一般我们在每一个node 都要选择方向;

整体的思路还是很简单的, 只要意识到我们这里并不是单纯的 DFS 就行了, 而是一个search guided by value range; 最后的速度是8(62), 还可以吧, 毕竟这个题目有点年头了; 试了一下, 好像这个就是最优解了;

另外感觉这个题目其实可以用 BFS 做? 自己不准备写这个代码了, 看看discussion 有没有人写;

这个是 discussion 一个版本:

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

他意识到这一题其实把recursive call放在上面会让代码更简练一些;

这个是一个 iterative 的: (因为是 BST而不是一个 general tree, BST 里面的搜索用 iterative 是完全很好做的)

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;   
        }  
    }  
};

就类似 Binary Search 那样的, 就是更新两个 pointer 就是了;
还可以写的更简单:

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;  
}

居然没有看到有人用 BFS 解; 难道要我自己写一个?
仔细想了一下, 好像 BFS 做不了: 因为你虽然用 BFS 可以用最快的速度发现两个 key, 但是你没有办法确定他们的 LCA; 观察我自己写的针对 general tree 的代码, 还是针对 BST 的代码, 一个共同的特点都是这个搜索是针对 path 的; 你 BFS 这个是没有 PATH 的概念的, 只有 DFS 的时候才能有 PATH 这个概念(虽然 BST 的时候只取一条 path);

Problem Description

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

    _______6______  
   /              \  
___2__          ___8__  

/ \ / \
0 _4 7 9
/ \
3 5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Difficulty:Easy
Category:Algorithms
Acceptance:38.81%
Contributor: LeetCode
Companies
amazon microsoft facebook twitter
Related Topics
tree
Similar Questions
Lowest Common Ancestor of a Binary Tree