LowestCommonAncestorOfABinarySearchTree2 [source code]

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

    public boolean contains(TreeNode root, TreeNode key) {
        if (root == null) return false;
        return root.val == key.val || contains(root.left, key) || contains(root.right, key);
    }
}
/******************************************************************************/

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

这个算法写的时候就知道肯定不是最优解, 不过还是想锻炼一下自己看看怎么写;
通用的思路还是一样的, 一个辅助的 recursion 来找到当前 node 的 subtree 左右两个分支是否包含要p 或者 q. 大概思路在 ver1的 note 里面都解释过了;

最后的速度是13(3), 非常不好, 不过是意料之中; 但是得到的锻炼还是很好的;

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