Lowest Common Ancestor II

题目：

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 attribute parent which point to the father of itself. The root's parent is null.

分析：

这道题目有父亲结点，我选择从A, B开始，同时向上走，并且记录他们经过的path，每走一步互相查询有没有交叉。

用这种方法要记得，当A == B的时候，需要结束程序。

解法：

class Solution {
public:
    /**
     * @param root: The root of the tree
     * @param A, B: Two node in the tree
     * @return: The lowest common ancestor of A and B
     */
    ParentTreeNode *lowestCommonAncestorII(ParentTreeNode *root,
                                           ParentTreeNode *A,
                                           ParentTreeNode *B) {
        // Write your code here
        if (root == NULL) {
            return root;
        }
        if (A == NULL) {
            return B;
        }
        if (B == NULL) {
            return A;
        }

        unordered_set<ParentTreeNode*> hashA;
        unordered_set<ParentTreeNode*> hashB;
        hashA.insert(A);
        hashB.insert(B);

        while (A != root && B != root) {
            A = A->parent;
            B = B->parent;
            if (A == B) {
                return A;
            }
            if (hashA.find(B) != hashA.end() ) {
                return B;
            }
            if (hashB.find(A) != hashB.end() ) {
                return A;
            }
            hashA.insert(A);
            hashB.insert(B);
        }

        while (B != root) {
            B = B->parent;
            if (hashA.find(B) != hashA.end() ) {
                return B;
            }
            hashB.insert(B);
        }

        while (A != root) {
            A = A->parent;
            if (hashB.find(A) != hashB.end() ) {
                return A;
            }
            hashB.insert(A);
        }

        return root;
    }
};