Leetcode/各大家 -- 236. Lowest Common Ancestor of a Binary Tree (Recursion+Iteration)

236. Lowest Common Ancestor of a Binary Tree (Recursion+Iteration)

• Difficulty: Medium

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

问题及相关题：http://rainykat.blogspot.com/2017/01/leetcode-235-lowest-common-ancestor-of.html

Company: Amazon LinkedIn Apple Facebook Microsoft

思路1： recursion: 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.

Complexity:  O(n) as the method does a simple tree traversal in bottom up fashion.
关键字： dfs

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||root==p||root==q) return root;
        TreeNode leftN = lowestCommonAncestor(root.left,p,q);
        TreeNode rightN = lowestCommonAncestor(root.right,p,q);
        if(leftN!=null&&rightN!=null) return root;//case:left is p/q and right is q/p root is LCA 
        if(leftN == null) return rightN;//case: p,q both in right subtree, right is LCA
        return leftN;//case: both in left, left is LCA
    }
}

思路2: Iterative: slow, but for better understanding
*Use HashMap to track <node, ancestor>
*Use Queue do BFS across the tree and update map, till find both p, q in tree
*After BFS, use set to find common ancestor of p,q

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null)return root;
        Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();//<node, ancestor>
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        map.put(root, null);
        queue.offer(root);
        //find p & q (|| in not condition)
        while(!map.containsKey(p) || !map.containsKey(q)){
            TreeNode cur = queue.poll();
            if(cur.left != null){
                map.put(cur.left, cur);
                queue.offer(cur.left);
            }
            if(cur.right != null){
                map.put(cur.right, cur);
                queue.offer(cur.right);
            }
        }
        //find common ancestor by storing one node and its all ancestors in the set
        Set<TreeNode> set = new HashSet<TreeNode>();
        while(p != null){//add p and ancestors till root
            set.add(p);
            p = map.get(p);
        }
        while(!set.contains(q)){
            q = map.get(q);
        }
        return q;
    }
}