285 inorder successor in BST

1012 ワード

inorder successorは中序遍歴の次のノードであり、左の子供の父親でもあり、
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;    
}