先用最ugly 最随心所欲的代码AC,基本思想是生成两个路径，然后找到最后一个相同的值，然后在BST中查找到这个值返回结点地址，最直观，最容易理解，代码相对啰嗦。
/**
* 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.上面的代码似乎很冗余，但是却非常好理解，在讨论区看到大神们的解法，可以说是非常high level了，利用二叉搜索树的特性：左子树 < 根节点 < 右子树
/**
* 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.