• ㊗️
• 大家
• offer
• 多多！

## Problem

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

The successor of a node p is the node with the smallest key greater than p.val.

Example 1:

Input: root = [2,1,3], p = 1
Output: 2
Explanation: 1's in-order successor node is 2. Note that both p and the return value is of TreeNode type.


Example 2:

Input: root = [5,3,6,2,4,null,null,1], p = 6
Output: null
Explanation: There is no in-order successor of the current node, so the answer is null.


Note:

If the given node has no in-order successor in the tree, return null. It’s guaranteed that the values of the tree are unique.

## Code

class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
TreeNode res = null;

while(root != null){
if(p.val < root.val){
res = root;
root = root.left;
} else {
root = root.right;
}
}

return res;
}
}

class Solution {
TreeNode pre;
TreeNode res;

public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if(root == null) return null;
if(root.left == null  && root.right == null) return null;

helper(root, p);
return res;
}

private void helper(TreeNode root, TreeNode target){
if(root == null) return;

helper(root.left, target);

if(pre == target){
res = root;
// 不要忘记给pre赋值，不然走到下一步pre仍然是target
pre = root;
return;
}

pre = root;

helper(root.right, target);
}
}

class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if(root == null) return null;

if(p.val < root.val){
// 结果一定在左边，但是当前的点可能是结果
TreeNode temp = inorderSuccessor(root.left, p);
// temp == null 表示没找到，所以就是当前点
return (temp == null) ? root : temp;
} else {
return inorderSuccessor(root.right, p);
}
}
}

class Solution:
def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
res = None

while root:
if root.val > p.val:
# 预留res为可能的结果
res = root
root = root.left
else:
root = root.right

return res

class Solution:
def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
stack = []
prev = False
while root or len(stack):
while root:
stack.append(root)
root = root.left

root = stack.pop()
if prev:
return root

if root.val == p.val:
prev = True

root = root.right

return None