问题
设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
如果指定节点没有对应的“下一个”节点，则返回null。
示例 1:
输入: root = [2,1,3], p = 1
2
/ \
1 3
输出: 2
示例 2:
输入: root = [5,3,6,2,4,null,null,1], p = 6
5
/ \
3 6
/ \
2 4
/
1
输出: null
思路
递归
p >= root：中序后继节点在右子树
p < root：左子树不为空就去左子树找，否则当前节点就是中序后继节点
代码
Python3
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> TreeNode:
if not root:
return None
# p >= root，后继节点在右子树
if root.val <= p.val:
return self.inorderSuccessor(root.right, p)
else:
# 左子树不为空
if self.inorderSuccessor(root.left, p):
return self.inorderSuccessor(root.left, p)
# 左子树为空，当前节点就是后继节点
else:
return root
