难度: Medium
设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
如果指定节点没有对应的“下一个”节点，则返回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
Submission
运行时间: 42 ms
内存: 19.6 MB
# 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 p.right:
pre, cur = p, p.right
while cur:
pre = cur
cur = cur.left
return pre
else:
successor = None
while root:
if p.val < root.val:
successor = root
root = root.left
elif p.val > root.val:
root = root.right
else:
break
return successor
Explain
此题解的思路基于二叉搜索树（BST）的中序遍历特性，即中序遍历会按照节点值的升序排列输出所有节点。根据题目要求，我们需要找到节点p的中序后继节点。解决方案分为两种情况：1. 如果节点p有右子节点，则p的后继节点是其右子树中的最左节点。2. 如果节点p没有右子节点，则向上寻找直到找到一个是其父节点的左子节点的节点，该父节点即为后继节点。如果一直向上回溯到根节点还没找到，那么该节点没有后继节点，返回null。
时间复杂度: O(h)，h为树的高度
空间复杂度: O(1)
# 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 p.right:
# 当节点p有右子节点，寻找其右子树的最左节点
pre, cur = p, p.right
while cur:
pre = cur
cur = cur.left
return pre
else:
# 当节点p无右子节点，向上寻找第一个大于p.val的节点
successor = None
while root:
if p.val < root.val:
successor = root
root = root.left
elif p.val > root.val:
root = root.right
else:
break
return successor
Explore
在二叉搜索树（BST）中，中序遍历的顺序是左子节点、当前节点、右子节点。当一个节点p有右子节点时，按照中序遍历的规则，接下来访问的节点应该是其右子树中的节点。在p的右子树中，最左边的节点是最小的节点，也就是在中序遍历中紧随p之后的节点。因此，p的后继节点是其右子树中的最左节点。
当节点p没有右子节点时，后继节点在上面的结构中。我们从树的根节点开始，向下搜索定位到节点p。在这个过程中，如果当前节点的值大于p的值，则有可能是p的后继节点，我们暂时记录这个节点，并继续向左子树搜索，因为我们需要找到比p大的最小节点。如果当前节点的值小于或等于p的值，则向右子树搜索。这个搜索过程中记录的最后一个值大于p的节点就是p的后继节点。
如果节点p是树中的最大节点，那么它没有右子节点，且在向上回溯寻找后继节点的过程中，不会找到一个值大于p的节点。在这种情况下，由于树中没有节点的值大于p的值，我们在搜索过程中记录的后继节点（successor）将始终为null。最终，算法返回null，表示p没有后继节点。