难度: Medium
给定一棵二叉搜索树和其中的一个节点 p ，找到该节点在树中的中序后继。如果节点没有中序后继，请返回 null 。
节点 p 的后继是值比 p.val 大的节点中键值最小的节点，即按中序遍历的顺序节点 p 的下一个节点。
示例 1：
输入：root = [2,1,3], p = 1 输出：2 解释：这里 1 的中序后继是 2。请注意 p 和返回值都应是 TreeNode 类型。
示例 2：
输入：root = [5,3,6,2,4,null,null,1], p = 6
输出：null
解释：因为给出的节点没有中序后继，所以答案就返回 null 了。
提示：
[1, 104] 内。-105 <= Node.val <= 105注意：本题与主站 285 题相同： https://leetcode-cn.com/problems/inorder-successor-in-bst/
运行时间: 37 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 not root:return None
# self.pre = None
# def dfs(root):
# if not root:
# return None
# if root.left:
# dfs(root.left)
# if self.pre == p:
# return root
# else:
# self.pre = root
# if root.right:
# dfs(root.right)
# return dfs(root)
# 参考
# https://leetcode.cn/problems/P5rCT8/solutions/1400725/053er-cha-sou-suo-shu-by-luna_-fcmz/
# 若当前节点值小于等于p节点值，则向右子树寻找
# 若当前节点值大于p节点值，则该节点可能为p的中序后继，但需要继续向左子树寻找是否有更小的
ans = None
while root != None:
if root.val > p.val:
ans = root
root = root.left
else:
root = root.right
return ans
此题解通过利用二叉搜索树的性质来寻找中序后继。根据二叉搜索树的特性，左子树的所有节点值都小于根节点，而右子树的所有节点值都大于根节点。因此，如果当前节点的值小于等于目标节点p的值，那么中序后继应该在右子树中；如果当前节点的值大于p的值，当前节点可能是中序后继，但还需要继续探索其左子树以确认是否存在更小但大于p的值的节点。通过这样的方式，我们可以确保找到的后继是比p节点值大中最小的一个。
时间复杂度: O(h)，其中 h 是树的高度。对于平衡的二叉搜索树，h=log(n)，而对于非平衡树，h可能接近n。
空间复杂度: 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':
# 初始化答案节点为None
ans = None
# 遍历树寻找中序后继
while root != None:
if root.val > p.val:
# 如果当前节点值大于p的值，更新答案并向左子树继续寻找
ans = root
root = root.left
else:
# 如果当前节点值不大于p的值，向右子树寻找
root = root.right
# 返回找到的中序后继，如果没有找到则为None
return ans
在算法实现中，当我们寻找中序后继时，如果节点p是树中的最大值，那么它的中序后继将不存在。该算法通过不断向右子树移动，直到无法继续移动（即`root`变为`None`）来处理这种情况。当我们遍历到最右边的节点（即最大值），并尝试访问其右子树时，由于右子树不存在，`root`将会变为`None`。在这种情况下，由于没有更新`ans`变量（因为没有找到更大的值），最终函数会返回`None`，符合题目要求的输出。
在中序遍历的过程中，任何节点的中序后继是比该节点值大的最小节点。因此，当当前节点的值大于目标节点p的值时，当前节点可能是一个合适的后继候选。然而，我们需要确定是否存在一个更小但仍然大于p的值的节点作为更适合的后继。这样的节点，如果存在，一定位于当前节点的左子树中，因为左子树中的所有节点都小于当前节点（但有可能大于p）。继续探索左子树可以帮助我们找到这样的节点，如果直接移动到右子树，可能会错过更合适的中序后继。
如果树结构发生改变，例如添加或删除节点，而树本身维持了二叉搜索树的属性，那么本算法依然有效。算法的正确性基于二叉搜索树的性质，即左子树中所有的值都小于根节点，右子树所有的值都大于根节点，以及中序遍历二叉搜索树会得到一个递增序列。只要这些性质被保持，即使树的具体结构变化了，算法仍然能正确地找到中序后继。然而，如果树的修改破坏了二叉搜索树的性质（例如，插入或删除后没有适当的重新平衡），则可能需要额外的操作来恢复或验证这些性质以保证算法的正确执行。