S******n
发帖数: 132 | 1 A binary search tree is given. Find the ceiling value present in the BST of
a given key. eg-
8
3 12
2 6 10 15
4
key - 13 => 15
key - 4 =>6
key - 8 =>10
自己写了一个
TreeNode* find(TreeNode* root, int target)
{
if(!root) return NULL;
TreeNode * result = NULL;
TreeNode* curr = root;
while( curr )
{
if(target >= curr->val)
curr = curr->right;
else
{
result = curr;
curr = curr->left;
}
}
return result;
}
谁帮我看看对不对，感觉离开leetcode的onlinejudge自己不会测试了 |
p*****2
发帖数: 21240 | 2
of
感觉curr变量可以不需要
【在 S******n 的大作中提到】
: A binary search tree is given. Find the ceiling value present in the BST of
: a given key. eg-
: 8
: 3 12
: 2 6 10 15
: 4
: key - 13 => 15
: key - 4 =>6
: key - 8 =>10
: 自己写了一个
|
S******n
发帖数: 132 | 3 是不需要，这个题目是不是也可以转化
有duplicate的BST找lowerbound和upperbound？
【在 p*****2 的大作中提到】
:
: of
: 感觉curr变量可以不需要
|
l*****a
发帖数: 14598 | 4 为什么不是找previous/next node with inorder traverse
【在 S******n 的大作中提到】
: 是不需要，这个题目是不是也可以转化
: 有duplicate的BST找lowerbound和upperbound？
|
c******a
发帖数: 789 | 5 我觉得正确。
若遇到小／相等的node，那肯定不是解，往右走。遇到大了的点，就拼命往它左边走。
走到走不动。 |
c******a
发帖数: 789 | 6 你这就O(n)了。楼主那个O(lgN)
【在 l*****a 的大作中提到】
: 为什么不是找previous/next node with inorder traverse
|
r**h
发帖数: 1288 | 7 感觉target=4的时候会走到4呀
of
【在 S******n 的大作中提到】
: A binary search tree is given. Find the ceiling value present in the BST of
: a given key. eg-
: 8
: 3 12
: 2 6 10 15
: 4
: key - 13 => 15
: key - 4 =>6
: key - 8 =>10
: 自己写了一个
|
l*****a
发帖数: 14598 | 8 真的吗?
【在 c******a 的大作中提到】
: 你这就O(n)了。楼主那个O(lgN)
|
l*****a
发帖数: 14598 | 9 result里面记的不是6?
【在 r**h 的大作中提到】
: 感觉target=4的时候会走到4呀
:
: of
|
S******n
发帖数: 132 | 10 往左走才update，应该是6啊
【在 l*****a 的大作中提到】
: result里面记的不是6?
|
|
|
l**d
发帖数: 746 | 11 这个还比较容易改，只要把等于的判断分开：等于的时候找右子树最左边的节点。
不过他这个算法只能从上往下找。如果输入6，应该返回root 8，好像就没办法了。
我觉得最直观的做法是in order traversal 变成一个sorted array，然后binary
search
【在 S******n 的大作中提到】
: 往左走才update，应该是6啊
|
S******n
发帖数: 132 | 12 如果是6的话会往右走，result并没有update还是会返回8
【在 l**d 的大作中提到】
: 这个还比较容易改，只要把等于的判断分开：等于的时候找右子树最左边的节点。
: 不过他这个算法只能从上往下找。如果输入6，应该返回root 8，好像就没办法了。
: 我觉得最直观的做法是in order traversal 变成一个sorted array，然后binary
: search
|
H****r
发帖数: 2801 | 13 key - 1
key - 16
应该返回啥？？？
of
【在 S******n 的大作中提到】
: A binary search tree is given. Find the ceiling value present in the BST of
: a given key. eg-
: 8
: 3 12
: 2 6 10 15
: 4
: key - 13 => 15
: key - 4 =>6
: key - 8 =>10
: 自己写了一个
|
l**d
发帖数: 746 | 14 实现了一下，的确是对的。往左走存下result设计不错。
【在 S******n 的大作中提到】
: 如果是6的话会往右走，result并没有update还是会返回8
|
l**d
发帖数: 746 | 15 1 返回 2阿
16我觉得可以返回Integer.MAXINT或者直接null
【在 H****r 的大作中提到】
: key - 1
: key - 16
: 应该返回啥？？？
:
: of
|
H****r
发帖数: 2801 | 16 这些edge case 需要确定吧，感觉1 返回2应该是不错， 16 可能直接throw error?
【在 l**d 的大作中提到】
: 1 返回 2阿
: 16我觉得可以返回Integer.MAXINT或者直接null
|
S******n
发帖数: 132 | 17 难道不是返回NULL吗？因为不存在
【在 H****r 的大作中提到】
: 这些edge case 需要确定吧，感觉1 返回2应该是不错， 16 可能直接throw error?
|
H****r
发帖数: 2801 | 18 不存在就返回NULL? 那小于最小的那个值也是吧...
【在 S******n 的大作中提到】
: 难道不是返回NULL吗？因为不存在
|
g**x
发帖数: 373 | 19 可以有O（lgN)的算法吗？
当BST为
1
2
3
4
...
如何O（lgN)呢？
在平均的情况下，in-order递归的方法也可以是O（lgN)，在worst情况下， 是O（N）。
【在 c******a 的大作中提到】
: 你这就O(n)了。楼主那个O(lgN)
|
c******a
发帖数: 789 | 20 我不明白了，in-order怎么都要从最小node开始，一个个按顺序走到最后的。相当于一
个array去遍历，怎么lgN啊？
严密一点一个balanced BST，楼主解法我还是觉得是lgN。 |
|
|
S******n
发帖数: 132 | 21 不平衡的bst怎么都是worst case O(n) |
t*******2
发帖数: 182 | 22 也写了一个，欢迎大牛们挑错~~~
先assume全是正数，找不到就return -1了
－－－－－－－－－－－－－－－－－－－－－－－－－－－
public int ceiling (Node root, int key) {
if (root == null) { // if reached the bottom and no value is greater
than target
return -1; // ceiling is not found
}
if (root.val == key) { // if key is found, return key
return root.val;
}
if(root.val < key) { // if root is smaller than key
return ceiling(root.right, key); // ceiling can only be in
right sub tree
}
int ceil = ceiling(root.left, key); // else search in left sub tree
return ceil >= key? ceil : root.val; // if there is no such value in
left, root is the ceiling
} |
g**x
发帖数: 373 | 23 when root->val < target, ceiling is definitely not in subtree of root.
when root->val > target, ceiling is definitely not in right subtree of root.
so no 遍历.
【在 c******a 的大作中提到】
: 我不明白了，in-order怎么都要从最小node开始，一个个按顺序走到最后的。相当于一
: 个array去遍历，怎么lgN啊？
: 严密一点一个balanced BST，楼主解法我还是觉得是lgN。
|
g**x
发帖数: 373 | 24 看不懂啊。自己写了个：
//
// return the pointer when a ceiling is found;
// otherwise, NULL;
//
TreeNode* find_ceiling(TreeNode* root, int target)
{
if (root==NULL) return NULL;
if (root->val > =target) {
TreeNode* temp = find_ceiling( root->left, target );
return (temp==NULL)? root: temp;
}
return find_ceiling( root->right, target );
}
greater
【在 t*******2 的大作中提到】
: 也写了一个，欢迎大牛们挑错~~~
: 先assume全是正数，找不到就return -1了
: －－－－－－－－－－－－－－－－－－－－－－－－－－－
: public int ceiling (Node root, int key) {
: if (root == null) { // if reached the bottom and no value is greater
: than target
: return -1; // ceiling is not found
: }
: if (root.val == key) { // if key is found, return key
: return root.val;
|
c******a
发帖数: 789 | 25 哦！明白了，相当于binary search。那的确是lgN
root.
【在 g**x 的大作中提到】
: when root->val < target, ceiling is definitely not in subtree of root.
: when root->val > target, ceiling is definitely not in right subtree of root.
: so no 遍历.
|
c******a
发帖数: 789 | 26 忽然觉得自己好迟钝，居然去怀疑lolhaha T_T |
x*****0
发帖数: 452 | |
