C++, dfs, not the best solution but easy to understand.

• ``````class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
foundP = false;
foundQ = false;
ret = NULL;
dfs(root,p,q);
return ret;
}
private:
bool foundP;
bool foundQ;
TreeNode *ret;

void dfs(TreeNode *root, TreeNode *p, TreeNode *q){
if(root == NULL) return;
bool state1 = foundP || foundQ;
dfs(root->left,p,q);
bool state2 = foundP ^ foundQ;
dfs(root->right,p,q);
bool state3 = foundP ^ foundQ;

if(root == p) foundP = true;
if(root == q) foundQ = true;
bool state4 = foundP && foundQ;

if(!state1 && state2 && !state3) ret = root;
else if(!state1 && state3 && state4) ret = root;
}
};
``````

I use 4 states to trace the dfs() process:

• State1: Before visit left child and right child
• State2: After finished `dfs(left child)`
• State3: After finished `dfs(two children)`
• State4: After dfs children, check root itself.

When can we judge that `root` is the ancestor?

##[1] root isn't one of (p,q)

• State1: Before visit left child and right child, found neither p nor q
• State2: Found one of p,q in `dfs(left child)`: `foundP == 0 && foundQ == 1` or `foundP == 1 && foundQ ==0` equals to `foundP ^ foundQ`
• State3: Found another in `dfs(right child)`: `foundP == 1 && foundQ == 1`

e.g. `tree = [1, 2 ,3]; p = 2; q = 3`

##[2] root is one of (p,q) or root == p == q

• State1: found none of (p,q)
• State2: we don't care.
• State3: After State3, only one of (p,q) is found OR None of them is found.
• State4: We check the value of `root`, and it equals to one of (p,q) OR both of p and q.
By now we have found p and q.

e.g. `tree = [1,2]; p = 1; q = 2`

###This solution can be optimized, but this version is clear. Hope this helps :)

*Another solution, using extra vector to save path

``````class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> pPath,qPath;
bool foundP = findPath(root,p,pPath);
bool foundQ = findPath(root,q,qPath);
if(!foundP && !foundQ) return NULL;
int loop = 0;
while(loop<pPath.size()&&loop<qPath.size()&&pPath[loop]==qPath[loop]) loop++;
if(pPath[loop-1]!=qPath[loop-1]) return NULL;
else return pPath[loop-1];
}

private:
bool findPath(TreeNode *root, TreeNode *find, vector<TreeNode*>& savePath){
if(root==NULL) return false;
savePath.push_back(root);
if(root == find) return true;
if(findPath(root->left,find,savePath)) return true;
if(findPath(root->right,find,savePath)) return true;
savePath.pop_back();
return false;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.