# 3 solutions with explanation

• The first one is straightforward but slow. The second one is also not difficult to come up with. The 3rd is neat and but it was hard for me to get my head around it at the first time.

``````   /**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return sol1(root,p,q);
//return sol2(root,p,q);
//return sol3(root,p,q);
}

// 23ms
TreeNode* sol3(TreeNode* root, TreeNode* p, TreeNode* q) {
// no p and q
if (!root) return NULL;
// find either p or q
if (root == p || root == q) return root;
TreeNode *left = sol3(root->left,p, q);
TreeNode *right = sol3(root->right,p,q);

// p and q are in different subtrees
if(left && right) return root;
// p and q are in the same subtree
return left ? left : right;
}

// 23ms   the lowest cross of the paths
TreeNode* sol2(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> p1, p2;
pathTo(root,p,p1);
// if q in the path
for (auto a : p1) {
if (q == a) return q;
}
pathTo(root,q,p2);
for (auto a : p2) {
if (p == a) return p;
}
// if p in the path
int N = p1.size();
int M = p2.size();

for (int i = N -1; i >= 0 ; i--) {
for (int j = M -1; j >=0 ;j--) {
if (p1[i] == p2[j]) {
return p1[i];
}
}
}

// should never come here
return NULL;
}

bool pathTo(TreeNode* root, TreeNode* n, vector<TreeNode*> &path) {
if (!root) return false;
if (root == n) {
path.push_back(n);
return true;
}

path.push_back(root);
if (pathTo(root->left, n, path)) return true;
if (pathTo(root->right,n, path)) return true;
path.pop_back();
return false;
}

//slow....
TreeNode* sol1(TreeNode* root, TreeNode* p, TreeNode* q) {
if (p == root || q == root) return root;
// 1 in left, 2 in right
int lp = dfsFind(root->left,p) ? 1 : 2;
int lq = dfsFind(root->left,q) ? 1 : 2;

if (lp != lq) return root;
if (lp == 1) return lowestCommonAncestor(root->left,p,q);
return lowestCommonAncestor(root->right, p, q);
}

bool dfsFind(TreeNode *root, TreeNode *t) {
if (!root) return false;
if (root == t) return true;
if (dfsFind(root->left,t)) return true;
return dfsFind(root->right,t);
}
};``````

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