二叉搜索树（BST）的中序后继节点查找问题

题目描述
给定一个二叉搜索树（BST）中的某个节点，需要找到它在中序遍历序列中的后继节点。中序遍历的后继节点定义为：在BST的中序遍历结果中，排在该节点之后的下一个节点。如果该节点已经是最后一个节点，则返回null（或等价的表示）。题目假设每个节点都有指向其父节点的引用（即树节点结构为node.left、node.right、node.parent），但如果没有父节点指针，则需要从根节点开始查找。这是二叉搜索树中的一个经典问题，常见于面试中。

解题过程循序渐进讲解

步骤1：理解中序遍历的顺序
首先，回顾BST的中序遍历：按照左子树 → 根节点 → 右子树的顺序访问，结果是升序排列的节点值序列。例如，对于下图BST：

       20
      /  \
     8    22
    / \
   4   12
      /  \
     10  14

中序遍历结果：4, 8, 10, 12, 14, 20, 22。

• 节点8的后继是10。
• 节点14的后继是20。
• 节点22的后继是null（最后一个节点）。

步骤2：分析后继节点的可能位置
给定节点p，其后继节点有两种情况：

1. 情况A：如果p有右子树，则后继节点是其右子树中的最小节点。
   原因：中序遍历中，访问p之后会立即遍历其右子树，而右子树的第一个节点就是其中的最小值节点。
   示例：节点12有右子树（包含14），右子树中最小节点是14，即后继。

2. 情况B：如果p没有右子树，则后继节点是第一个“祖先”，使得p位于该祖先的左子树中。
   原因：如果p没有右子树，意味着中序遍历在访问p后需要“回溯”到某个祖先，这个祖先节点是尚未被访问的、且其左子树中包含p。如果回溯到根节点仍找不到这样的祖先，则p是最后一个节点。
   示例：节点10无右子树，它的父节点是12，但10是12的左子节点吗？是的，所以后继是12。
   示例：节点14无右子树，它的父节点是12，但14是12的右子节点，所以继续向上：12的父节点是8，而12是8的右子节点，继续向上：8的父节点是20，而8是20的左子节点，找到！后继是20。

步骤3：算法设计（有父节点指针）
假设树节点定义如下：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None

查找后继的算法：

function findInorderSuccessor(p):
    if p is None: return None
    
    // 情况A: 有右子树
    if p.right is not None:
        curr = p.right
        while curr.left is not None:
            curr = curr.left
        return curr
    
    // 情况B: 无右子树
    curr = p
    parent = p.parent
    while parent is not None and parent.right == curr: // 当curr是父节点的右子节点时继续向上
        curr = parent
        parent = parent.parent
    return parent  // 如果parent为None，表示p是最后一个节点

解释：

• 在情况B的循环中，parent.right == curr表示当前节点curr是其父节点的右子节点，这意味着父节点已经在curr之前被访问过了（因为中序遍历顺序是：左、根、右，访问父节点后才访问其右子树）。所以需要继续向上，直到curr是某个祖先的左子节点，此时该祖先就是后继。

步骤4：示例推演
以节点14为例（无右子树）：

• curr = 14, parent = 12。parent.right (12的右子节点) == curr(14)为真，所以向上：curr = 12, parent = 8。
• 现在parent.right (8的右子节点) == curr(12)为真，继续向上：curr = 8, parent = 20。
• 现在parent.right (20的右子节点) == curr(8)为假（8是20的左子节点），循环结束，返回parent = 20，即后继。

步骤5：算法设计（无父节点指针）
如果没有父节点指针，就需要从根节点开始搜索。思路是：从根节点向下遍历，同时记录可能的候选后继（即“最后一个左转的节点”）。
算法：

function findSuccessor(root, p):
    if p.right exists:
        return findMin(p.right)
    
    successor = None
    curr = root
    while curr is not None:
        if p.val < curr.val:  // p在curr的左子树中
            successor = curr  // curr是潜在的候选项
            curr = curr.left
        elif p.val > curr.val: // p在curr的右子树中
            curr = curr.right
        else: // 找到p，退出循环
            break
    return successor

解释：

• 当p.val < curr.val时，说明p在curr的左子树中，此时curr可能是p的后继（因为中序遍历中curr在p之后访问）。我们记录curr，然后继续向左子树搜索。
• 当p.val > curr.val时，p在右子树中，curr不可能是后继（因为curr在p之前访问），直接向右搜索。
• 当找到p时，如果p有右子树，已经在第一步处理；如果没有，则返回记录的successor。

步骤6：时间与空间复杂度

• 时间复杂度：O(h)，其中h是树的高度。在平衡BST中为O(log n)，在最坏情况（链状树）中为O(n)。
• 空间复杂度：O(1)，只使用了常数个指针。

步骤7：边界情况

• 如果节点是最后一个节点（如最大值节点），返回None。
• 如果树为空或节点为None，返回None。
• 如果节点是根节点且无右子树，且没有左转祖先，返回None。

总结
查找BST中序后继的关键是分情况讨论：有右子树时找右子树的最小节点；无右子树时向上找到第一个“左祖先”。掌握这个逻辑，并注意有无父节点指针的实现差异，就能解决此类问题。