邻居家太郁闷了# Living
r*e
1 楼
国内小伙伴，刚面fb，分享一下题目和答案
给一个bst，和其中一个节点的value，求在bst中比这个节点大的下一个node
，O(1) space和 O(log N) time的解法，有Parent指针
struct node{
int val;
node* left;
node* right;
node* parent;
node(int v){
val = v;
parent = left = right = NULL;
}
};
node* find(node* root, int val){
if(!root) return NULL;
if(root->val == val) return root;
if(root->val < val) return find(root->right, val);
return find(root->left, val);
}
node* next(node* n){
if(!n) return NULL;
if(n->right){
node* p = n->right;
while(p->left) p = p->left;
return p;
}
p = n->parent;
while(p){
if(p->left == n) break;
n = p;
p = p->parent;
}
return p;
}
给一个bst，和其中一个节点的value，求在bst中比这个节点大的下一个node
，O(1) space和 O(log N) time的解法，有Parent指针
struct node{
int val;
node* left;
node* right;
node* parent;
node(int v){
val = v;
parent = left = right = NULL;
}
};
node* find(node* root, int val){
if(!root) return NULL;
if(root->val == val) return root;
if(root->val < val) return find(root->right, val);
return find(root->left, val);
}
node* next(node* n){
if(!n) return NULL;
if(n->right){
node* p = n->right;
while(p->left) p = p->left;
return p;
}
p = n->parent;
while(p){
if(p->left == n) break;
n = p;
p = p->parent;
}
return p;
}
