题目: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:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if((root == NULL) || (p == NULL) || (q == NULL))
return NULL;
TreeNode * curNode = root;
if(p -> val > q -> val)
{
while(curNode != NULL)
{
if(curNode -> val > p -> val)
{
curNode = curNode -> left;
}
else if(curNode -> val < q -> val)
{
curNode =curNode -> right;
}
else
return curNode;
}
}
else if(p -> val < q -> val)
{
while(curNode != NULL)
{
if(curNode -> val > q -> val)
{
curNode = curNode -> left;
}
else if(curNode -> val < p -> val)
{
curNode =curNode -> right;
}
else
return curNode;
}
}
return NULL;
}
};