d********e
发帖数: 321 | 1 最近遇到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;
} |
s*****p
发帖数: 30 | 2 这道题的思路和 BST 查找 ceiling， floor 的思路一样的吧， 到geeksforgeeks上面
搜就有了 |
m**********1
发帖数: 52 | 3 public static Integer findNextLowest(TreeNode root, int target) {
if (root == null) {
return Integer.MIN_VALUE;
} else if (root.val >= target) {
return findNextLowest(root.left, target);
} else if (root.val < target) {
return Math.max(root.val, findNextLowest(root.right, target));
} else {
return root.val;
}
}
【在 d********e 的大作中提到】
: 最近遇到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;
|
d********e
发帖数: 321 | 4 这个代码的最后一个else 貌似是never hit啊，还有给的target value可能不在树上
【在 m**********1 的大作中提到】
: public static Integer findNextLowest(TreeNode root, int target) {
: if (root == null) {
: return Integer.MIN_VALUE;
: } else if (root.val >= target) {
: return findNextLowest(root.left, target);
: } else if (root.val < target) {
: return Math.max(root.val, findNextLowest(root.right, target));
: } else {
: return root.val;
: }
|
h*********n
发帖数: 11319 | 5 如果不在树上那
TreeNode* inorderSuccessor(TreeNode* root, target t) {
if (root == NULL || p == NULL) return NULL;
TreeNode *suc = NULL;
while (root != NULL) {
if (root->val <= t) {
root = root->right;
} else {
suc = root;
root = root->left;
}
}
return suc;
}
target不在树上的话应该必须O（N）了
【在 d********e 的大作中提到】
: 这个代码的最后一个else 貌似是never hit啊，还有给的target value可能不在树上
|
s*******a
发帖数: 8 | 6 不在树上也是lgn。这个函数在树里，每层只看一个元素。所以树的高度就是复杂度
【在 h*********n 的大作中提到】
: 如果不在树上那
: TreeNode* inorderSuccessor(TreeNode* root, target t) {
: if (root == NULL || p == NULL) return NULL;
:
: TreeNode *suc = NULL;
: while (root != NULL) {
: if (root->val <= t) {
: root = root->right;
: } else {
: suc = root;
|
s*******i
发帖数: 406 | 7 private static TreeNode findNextLowest(TreeNode root, int target){
TreeNode node = root;
TreeNode res = null;
while(node != null){
if(node.val >= target){
node = node.left;
}
if(node.val < target){
res = node;
node = node.right;
}
}
return res;
} |
