http://www.lintcode.com/en/problem/lowest-common-ancestor-ii/\#

1. use recursion. u could follow the same logic to use divide and conquer to travers the tree once.

public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root,
                                                 ParentTreeNode A,
                                                 ParentTreeNode B) {
        // Write your code here  
        if (root == null) {
            return null;
        }

        if (root == A || root == B) {
            return root;
        }

        ParentTreeNode left = lowestCommonAncestorII(root.left, A, B);
        ParentTreeNode right = lowestCommonAncestorII(root.right, A, B);

        if (left == null) {
            return right;
        }

        if (right == null) {
            return left;
        }

        return root;




    }

1. use non-recursion. list down the path from bottom up and compare it in a loop.

public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root,
                                                 ParentTreeNode A,
                                                 ParentTreeNode B) {
        // Write your code here
        ArrayList<ParentTreeNode> aList = getPathUp(A);
        ArrayList<ParentTreeNode> bList = getPathUp(B);

        int aIndex = aList.size() - 1;
        int bIndex = bList.size() - 1;

        ParentTreeNode ans = root;
        while (aIndex >= 0 && bIndex >= 0) {
            if (aList.get(aIndex) != bList.get(bIndex)) {
                break;
            }

            ans = aList.get(aIndex);

            aIndex--;
            bIndex--;

        }

        return ans;
    }

    public ArrayList<ParentTreeNode> getPathUp(ParentTreeNode root) {
        ArrayList<ParentTreeNode> ans = new ArrayList<>();
        ParentTreeNode node = root;
        while (node != null) {
            ans.add(node);
            node = node.parent;
        }
        return ans;
    }