Given the root and two nodes in a Binary Tree. Find the lowest common ancestor(LCA) of the two nodes.

The lowest common ancestor is the node with largest depth which is the ancestor of both nodes.

The node has an extra attributeparentwhich point to the father of itself. The root's parent is null.

Example

For the following binary tree:

  4
 / \
3   7
   / \
  5   6

LCA(3, 5) =4

LCA(5, 6) =7

LCA(6, 7) =7

1. 这个树没有value只有一个reference to its own parents， 所以我们可以从两个结点往上找，用一个hashset如果出现过了元素，则那个元素就是LCA, 如果一直都没有，则root是LCA

public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root,
                                                 ParentTreeNode A,
                                                 ParentTreeNode B) {
        // Write your code here   


        HashSet<ParentTreeNode> sets = new HashSet<>();

        while (A.parent != null || B.parent != null) {
            if (A.parent != null) {
                if (!sets.add(A)){
                    return A;
                } else {
                    A = A.parent;
                }
            }
            if (B.parent != null) {
                if (!sets.add(B)) {
                    return B;
                } else {
                    B = B.parent;
                }
            }
        }

        if (A.parent == null) {
            return A;
        }

        if (B.parent == null) {
            return B;
        }

        return root;





    }

1. 用两个list 从底往上找， 然后比较两个list

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

        findPath(aList, A);
        findPath(bList, B);
        int i = aList.size() - 1;
        int j = bList.size() - 1;
        while (aList.get(i) == bList.get(j)) {
            if (i == 0) {
                return aList.get(i);
            }
            if (j == 0) {
                return bList.get(j);
            }

            i--;
            j--;
        }

        return aList.get(i + 1);




    }

    public void findPath(ArrayList<ParentTreeNode> path, ParentTreeNode A) {
        if (A == null) {
            return;
        }

        path.add(A);
        findPath(path, A.parent);
    }