``````/**
* 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) {
vector<int> m,n;
TreeNode * pp = root,*qq = root;
while(pp)
{
m.push_back(pp->val);
if(pp->val > p->val)
pp = pp->left;
else if (pp->val < p->val)
pp = pp->right;
else
break;
}

while(qq)
{
n.push_back(qq->val);
if(qq->val > q->val)
qq = qq->left;
else if (qq->val < q->val)
qq = qq->right;
else
break;
}

int res;
for(int i = 0;i<min(m.size(),n.size());i++)
{

if(m[i] != n[i])
{
break;
}

res = m[i];
}

while(root)
{
if(root->val == res)
return root;
else if (root->val < res)
root = root->right;
else
root = root->left;
}

return NULL;
}
};``````

``````Runtime: 32 ms, faster than 88.46% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
Memory Usage: 23.9 MB, less than 42.56% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.``````

``````/**
* 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 {
private:
TreeNode * generate_path(vector<int> & path,TreeNode *root,TreeNode *target)
{
while(root)
{
path.push_back(root->val);
if(root->val > target->val)
root = root->left;
else if (root->val < target->val)
root = root->right;
else
break;
}

return root;
}

TreeNode * search_target(TreeNode *root,int target)
{
while(root)
{
if(root->val > target)
root = root->left;
else if (root->val < target)
root = root->right;
else
break;
}

return root;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<int> ppath,qpath;
int target;
TreeNode * pp = generate_path(ppath,root,p);
TreeNode * qq = generate_path(qpath,root,q);

for(int i = 0;i<min(ppath.size(),qpath.size());i++)
{
if(ppath[i] != qpath[i])
{
break;
}
target = ppath[i];
}

return search_target(root,target);
}
};``````

``````Runtime: 32 ms, faster than 88.16% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
Memory Usage: 23.9 MB, less than 43.82% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.``````

``````/**
* 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) {
//p q均在左子树
if(p->val < root->val && q->val < root->val)
return lowestCommonAncestor(root->left,p,q);
//p q均在右子树
else if (p->val > root->val && q->val > root->val)
return lowestCommonAncestor(root->right,p,q);
else
return root;
}
};``````

``````Runtime: 24 ms, faster than 99.43% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
Memory Usage: 23.9 MB, less than 43.82% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
Next challenges:``````

``````/**
* 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) {
while(root)
{
if(root->val < p->val && root->val < q->val)
root = root->right;
else if (root->val > p->val && root->val > q->val)
root = root->left;
else
return root;
}

return NULL;
}
};``````

``````Runtime: 32 ms, faster than 88.16% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.
Memory Usage: 23.8 MB, less than 43.82% of C++ online submissions for Lowest Common Ancestor of a Binary Search Tree.``````