Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”
_______6______
/ \
___2__ ___8__
/ \ / \
0 _4 7 9
/ \
3 5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
这个题目的意思就是：让你找出两个结点最近的祖先，也就是和他们血缘关系最近的祖先
我的解法：深度优先搜索，再以这个结点，进行搜索，如果以这个结点进行搜索时，发现了我们要求的两个结点，则该结点就是这两个结点最近的 ，不过我的算法的时间复杂度很高。。。。
/**
* 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:
void dfs(TreeNode *root, TreeNode *p, TreeNode *q,int &i)
{
if (root == NULL)return;
if (root == p || root == q)
++i;
dfs(root->left, p, q,i);
dfs(root->right, p, q,i);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
map<TreeNode*,int> visited;
stack<TreeNode*> sttn;
TreeNode * curNode;
sttn.push(root);
while (!sttn.empty())
{
curNode = sttn.top();
while(curNode->left != NULL&&visited[curNode->left] != )
{
curNode = curNode->left;
sttn.push(curNode);
}
if (curNode->right != NULL&&visited[curNode->right] != )
{
curNode = curNode->right;
sttn.push(curNode);
}
else
{
int cnt = ;
dfs(curNode, p, q,cnt);
if (cnt == )
return curNode;
visited[curNode] = ;
sttn.pop();
}
}
}
};