https://leetcode.com/problems/inorder-successor-in-bst/description/
image.png
这道题如何思考。
我们可以发现，如果根节点的值和P的值一样的时候，下一个值无非就是跟节点右子树的最左端。如果根节点比P大，我们应该去右边找和P一样大的节点。
如果小，就去左边找。
有了这个思路，基本就可以把代码写出来了。首先需要一个GETMIN的方法，用来找右子树的最左端。
由第一个EXAMPLE，我们还能发现，如果右子树为NULL。那么如果有PARENT，就应该返回PARENT。
所以我们在往左走的时候，还需要记录PARENT是谁。
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if(root == null) return null;
if(p.val<root.val){
TreeNode left = inorderSuccessor(root.left,p);
return left == null? root : left;
}else if(p.val>root.val){
return inorderSuccessor(root.right,p);
}else{
return getMin(root.right);
}
}
private TreeNode getMin(TreeNode cur){
if(cur == null) return null;
while(cur.left != null)
cur = cur.left;
return cur;
}
通过观察，我们可以发现，=和》都需要向右走。走完后直到右边的VAL比它大了，又要开始向左走。就可以压缩相同逻辑。
TreeNode par = null;
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if(root == null) return par;
if(p.val >= root.val){
return inorderSuccessor(root.right,p);
}else{
par = root;
return inorderSuccessor(root.left,p);
}
}
