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;
}