285 inorder successor in BST
1012 ワード
inorder successorは中序遍歴の次のノードであり、左の子供の父親でもあり、
ret変数はrootの父のノードを記録し、whileループが終了すると、元のroot=NoneまたはpがBSTに存在しない場合(root=None)、Noneがpを見つけた後に戻り、pに右の息子がいない場合、最初の大きな数字は記録したばかりのretがpを見つけた後、右の息子がいれば右の木の一番左の値(最小値)を見つけます.
ret変数はrootの父のノードを記録し、whileループが終了すると、元のroot=NoneまたはpがBSTに存在しない場合(root=None)、Noneがpを見つけた後に戻り、pに右の息子がいない場合、最初の大きな数字は記録したばかりのretがpを見つけた後、右の息子がいれば右の木の一番左の値(最小値)を見つけます.
struct TreeNode * inorderSuccessor(struct TreeNode *root,struct TreeNode* p)
{
if (root == NULL || p == NULL) {
return NULL;
}
struct TreeNode *ret = NULL;
while (root && root->val != p->val) {
if (p->val < root->val) {
ret = root;
root = root->left;
}
else {
root = root->right;
}
}
if(root == NULL) //not found
return NULL;
if(root->right == NULL)
return ret;
root = root.right //
while(root->left!=NULL)
root = root->left;
return root;
}