Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
“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).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Solution1：post-order / 分治 遞歸

思路：因為題目中是說給given two nodes音比，說明并一定在tree里面 且 是reference所以不會有重復(fù)多次匹配情況织堂。
所以可以比較巧妙地 分治divide只分別關(guān)注sub_left_tree和sub_right_tree中先碰到的任意兩者之一的位置箭阶，conquer時情況1如果左右都找到(必定一個是p一個是q的位置)則向上返回當(dāng)前root作為目前LCA，情況2如果左或右只找到一個位置(說明兩個都在這個位置的子樹下 或是 只有一個在) 就向上返回這個位置(以后這個位置會被更新if 另一個在別的地方找到(那個root點的情況1))聘裁。
Time Complexity: O(N) Space Complexity: O(N) 遞歸緩存

Solution2：Iterative

思路：iterative 遍歷的同時需要將parent關(guān)系保存下來
(1) 建立parent map
(2) 在parent中尋找p q 的 LCA

屏幕快照 2017-09-08 下午1.15.50.png

Time Complexity: O(N) Space Complexity: O(N)

Solution3：post-order / 分治 遞歸 自Round1

Time Complexity: O(N) Space Complexity: O(N) 遞歸緩存

Solution1 Code：

class Solution1 {
    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)
            return right;
        else if (right == null)
            return left;
        else
            return root;
    }
}

Solution2 Code：

public class Solution2 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        
        parent.put(root, null);
        stack.push(root);
        while (!parent.containsKey(p) || !parent.containsKey(q)) {
            TreeNode node = stack.pop();
            if (node.left != null) {
                parent.put(node.left, node);
                stack.push(node.left);
            }
            if (node.right != null) {
                parent.put(node.right, node);
                stack.push(node.right);
            }
        }
        
        Set<TreeNode> ancestors = new HashSet<>();
        while (p != null) {
            ancestors.add(p);
            p = parent.get(p);
        }
        
        while (!ancestors.contains(q))
            q = parent.get(q);
        return q;
    }
}

Solution3_Round1 Code：

class Solution {
    
    class Pack {
        public boolean p;
        public boolean q;

        Pack() {
            p = false;
            q = false;
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return dfs(root, p, q, new Pack());
    }
    
    private TreeNode dfs(TreeNode root, TreeNode p, TreeNode q, Pack pack) {
        // terminal
        if(root == null) return null;
        
        // divide
        Pack pack_left = new Pack();
        TreeNode result_left = dfs(root.left, p, q, pack_left);
        if(result_left != null) return result_left;
        
        Pack pack_right = new Pack();
        TreeNode result_right = dfs(root.right, p, q, pack_right);
        if(result_right != null) return result_right;
        
        // conquer
        pack.p = pack_left.p || pack_right.p;
        pack.q = pack_left.q || pack_right.q;
        
        if(root == p) {
            pack.p = true;
        }
        else if(root == q) {
            pack.q = true;
        }
        
        if(pack.p && pack.q) {
            return root;
        }
        return null;
        
    }
}