Lowest Common Ancestor II

Lowest Common Ancestor II.png

解題思路 ：

既然有給 parent 的指針 先把 A 點跟 Ａ所有 parents 都存入 set (搜尋快速 O(1)) 接著在檢查 B 點跟 B 的所有 parents 有沒有出現在剛剛存的清單之中

C++ code :

<pre><code>
/**

• Definition of ParentTreeNode:
• class ParentTreeNode {
• public:

• int val;
  

• ParentTreeNode *parent, *left, *right;
  

• }
  */

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
    unordered_set<ParentTreeNode*> checked;
    while(A){
        checked.insert(A);
        A = A->parent;
    }
    while(B)
    {
        if(checked.count(B)) return B;
        B = B->parent;
    }
}

};