二叉搜索树（BST）的中序后继查找

题目描述
给定一棵二叉搜索树（BST）和其中一个节点 p，要求找到该节点在中序遍历序列中的后继节点（即中序遍历中紧挨着 p 的下一个节点）。假设每个节点包含 val（值）、left（左子节点）、right（右子节点）和 parent（父节点）指针。若 p 没有后继节点，则返回 null。

解题过程

步骤1：理解中序遍历与后继节点的定义

• 二叉搜索树的中序遍历结果是一个升序排列的序列。
• 节点 p 的后继节点是中序遍历中排在 p 之后的最小节点。
• 示例：对于中序遍历 [2, 3, 5, 7, 9]，若 p=5，则后继节点为 7；若 p=9，则后继节点为 null。

步骤2：分析后继节点的可能位置
后继节点的位置分两种情况：

1. p 有右子树：

   • 后继节点是 p 的右子树中的最左节点（即右子树中的最小值节点）。
   • 原因：中序遍历在访问 p 后，会立即遍历其右子树的最左侧分支。
   • 示例：若 p 的右子节点为 r，则从 r 开始一直向左查找，直到叶子节点。

2. p 无右子树：

   • 后继节点是 p 的某个祖先节点，且该祖先是其父节点的左子节点。
   • 原因：中序遍历在访问完 p 后，需要回溯到第一个“尚未处理右子树”的祖先。
   • 查找方法：从 p 开始向上遍历，直到找到某个节点 x，使得 p 位于 x 的左子树中。此时 x 即为后继。

步骤3：算法实现

• 若 p.right != null：
  • 从 p.right 出发，一直向左遍历，返回最底层的左子节点。
• 若 p.right == null：
  • 从 p 开始向上遍历，直到找到某个节点 x，满足 p 是 x 的左子节点（即 x.left == p）。
  • 若遍历到根节点仍未找到，说明 p 是最后一个节点，返回 null。

步骤4：代码示例（含详细注释）

def find_inorder_successor(p):
    if not p:
        return None
    
    # 情况1：p有右子树
    if p.right:
        node = p.right
        while node.left:  # 寻找右子树的最左节点
            node = node.left
        return node
    
    # 情况2：p无右子树
    else:
        # 向上查找第一个使p位于左子树的祖先
        node = p
        while node.parent and node.parent.right == node:
            node = node.parent  # 若p是父节点的右子节点，继续向上
        return node.parent  # 此时node的父节点就是后继

步骤5：示例验证
以如下BST为例（括号内为父节点指针）：

       5 (null)
      / \
    3 (5)  8 (5)
   / \    / \
  2 (3) 6 (8) 9 (8)
     \    \
    4 (3)  7 (6)

• 若 p=4（无右子树）：向上找到 3（4 是 3 的右子节点），继续向上找到 5（3 是 5 的左子节点），后继为 5。
• 若 p=5（有右子树）：进入右子树 8，然后向左找到 6，后继为 6。
• 若 p=9（无右子树）：向上找到 8（9 是 8 的右子节点），继续向上找到 5（8 是 5 的右子节点），无符合条件的祖先，返回 null。

关键点总结

• 通过父指针可高效回溯祖先节点，若无父指针需从根节点重新遍历（时间复杂度升至 O(n)）。
• 算法平均时间复杂度为 O(log n)，最坏情况（树退化为链表）为 O(n)。