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;
}
}
};
