285 inorder successor in BST

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;    
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容