Lowest Common Ancestor of a Binary Search Tree

without parent pointer lc 236

The idea is to traverse the tree starting from root. If any of the given keys (n1 and n2) matches with root, then root is LCA (assuming that both keys are present). If root doesn’t match with any of the keys, we recur for left and right subtree. The node which has one key present in its left subtree and the other key present in right subtree is the LCA. If both keys lie in left subtree, then left subtree has LCA also, otherwise LCA lies in right subtree.

time complexity: o(n)， 空间是栈高度O(logn)

这里假设node都在tree里面

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left =  lowestCommonAncestor(root.left, p, q);
        TreeNode right =  lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null){
            return root;
        }
        if(left == null )return right;
        return left;


    }
}

with parent pointer

public TreeNode lca(TreeNode p, TreeNode q){
    HashSet<TreeNode> set = new HashSet<TreeNode>();

    while ( p != null){
        set.add(p);
        p = p.parent;
    }
    while ( q != null ){        
        if ( set.contains(q)){
            return q;
        }else {
            q = q.parent;
        }
    }
    return null;
}

Lowest Common Ancestor of a Binary Search Tree lc235

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

新题

leetcode上面Lowest Common Ancestor of a Binary Tree变种题 其中函数要改成 public TreeNode lowestCommonAncestor(TreeNode root,set set) 就是找一个set里面所有的子节点 的共同祖先

   public TreeNode lowestCommonAncestor2(TreeNode root, set<TreeNode> set) {
        if(root == null){
            return null;
        }else if(set.contains(root)){
            return root;
        }else{
            TreeNode left = lowestCommonAncestor(root.left, set<TreeNode> set);
            TreeNode right = lowestCommonAncestor(root.right, set<TreeNode> set);
            if(left == null && right == null){
                return null;
            }else if(left == null){
                return right;
            }else if(right == null){
                return left;
            }else{
                return root;
            }

        }