s******n
发帖数: 65 | 1 突然想到一个题目，找到BST中离目标最近的那个数
大家又什么好解法？ | s*****y
发帖数: 897 | 2 I saw this question on this board 2-3 weeks ago.
【在 s******n 的大作中提到】
: 突然想到一个题目，找到BST中离目标最近的那个数
: 大家又什么好解法？
| g**u
发帖数: 583 | 3
假设该元素不在BST中，首先找到最后一个比该元素小的节点，然后找到第一个比该元素大的节点，返回2个节点中离目标最近的节点。
下面是实现，等待拍砖。
node * findClose(node *root, int value)
{
if(!root)
return NULL;
node * smaller=findLastSmaller(root, value);
node * greater=findFirstGrearer(root, value);
//we will also need to check both of smaller and greater are not NULL
return value-smaller->value< greater->value - value?smaller:greater;
}
node * findLastSmaller(node * root, int value)
{
if(!root)
return NULL;
node * result=NULL;
while(root)
{
if(root->value >= value)
root=root->left;
else{
result=root;
root=root->right;
}
}
return result;
}
node * findFirstGreater(node * root, int value)
{
if(!root)
return NULL;
node * result=NULL;
while(root)
{
if(root->value<=value)
root=root->right;
else{
result=root;
root=root->left;
}
}
return result;
}
时间复杂度是 O(log n), 空间复杂度是O(1)
还有一个做法就是in-order visit,然后做binary search， 找到该元素的区间，然后寻找目标节点。 时间复杂度是一样的，但空间复杂度就是 O(n)了
【在 s******n 的大作中提到】
: 突然想到一个题目，找到BST中离目标最近的那个数
: 大家又什么好解法？
|
|
