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