d********e
发帖数: 321 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: dilettante (半瓶醋), 信区: JobHunting
标 题: BST查找next lowest 可以达到 O(lg N)？
发信站: BBS 未名空间站 (Thu May 25 16:27:02 2017, 美东)
最近遇到next lowest的题，我写了下面这个inorder traversal (largest ->
smallest)的代码，但是对方坚持让我写 O(lg N)，但是TreeNode 只有 left, right
pointer，没有parent pointer, 我觉得不可能啊，大牛有啥好办法吗？
public static Integer findNextLowest(TreeNode root, int target) {
Stack stack = new Stack<>();
TreeNode cur = root;
while (cur != null || stack.size() > 0) {
while (cur != null) {
stack.push(cur);
cur = cur.right;
}
TreeNode node = stack.pop();
if (node.val < target) return node.val; // found the next lowest
cur = node.left;
}
return null;
} | l**********0
发帖数: 150 | | w********m
发帖数: 1137 | 3 把parent pointer放到argument里面吧 | s*******i
发帖数: 406 | 4 private static TreeNode findNextLowest(TreeNode root, int target){
TreeNode node = root;
TreeNode res = null;
while(node != null){
while(node != null && node.val >= target){
node = node.left;
}
while(node != null && node.val < target){
res = node;
node = node.right;
}
}
return res;
} | N********n
发帖数: 8363 | 5 Define "next lowest". And what's this "root"? A sorted tree, a heap
or sth?
【在 d********e 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: dilettante (半瓶醋), 信区: JobHunting
: 标 题: BST查找next lowest 可以达到 O(lg N)？
: 发信站: BBS 未名空间站 (Thu May 25 16:27:02 2017, 美东)
: 最近遇到next lowest的题，我写了下面这个inorder traversal (largest ->
: smallest)的代码，但是对方坚持让我写 O(lg N)，但是TreeNode 只有 left, right
: pointer，没有parent pointer, 我觉得不可能啊，大牛有啥好办法吗？
: public static Integer findNextLowest(TreeNode root, int target) {
: Stack stack = new Stack<>();
: TreeNode cur = root;
|
|
