[递归]面试题 04.06. 后继者(medium)

递归]面试题 04.06. 后继者(medium)"/>

[递归]面试题 04.06. 后继者(medium)

题目：

题解：

代码如下：

class Solution {
public:// 由于BST的中序遍历对应的递增数组，所以当 p->val >= root->val 时，我们需要在右子树中找后继节点// 而当 p->val < root->val 时，我们需要在左子树中寻找后继节点// 若能在左子树中找到后继节点，则返回后继节点，否则根节点root就是后继节点，因为这说明p的右孩子为空TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {if(!root||!p)return nullptr;if(p->val>=root->val)return inorderSuccessor(root->right,p);else{TreeNode *left=inorderSuccessor(root->left,p);return left?left:root;}}
};