s******n 发帖数: 65 | 1 突然想到一个题目,找到BST中离目标最近的那个数
大家又什么好解法? | s*****y 发帖数: 897 | 2 I saw this question on this board 2-3 weeks ago.
【在 s******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 突然想到一个题目,找到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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 突然想到一个题目,找到BST中离目标最近的那个数 : 大家又什么好解法?
|
|