二叉搜索树的中序前驱查找

题目描述
在二叉搜索树（BST）中，给定一个节点，找出其中序遍历序列中的前驱节点。中序遍历的前驱节点定义为：在中序遍历顺序下，比该节点值小的最大节点。如果该节点没有前驱（例如它是树中的最小节点），则返回 null。

知识点

• 二叉搜索树的性质：左子树所有节点值 < 根节点值 < 右子树所有节点值，中序遍历结果为升序序列。
• 前驱节点的定位逻辑，涉及树结构的遍历与条件判断。

解题过程循序渐进讲解

第一步：理解中序遍历顺序与前驱定义

1. 回顾二叉搜索树的中序遍历：左子树 → 根节点 → 右子树，结果是节点值升序排列。
2. 对于节点 p，其前驱节点就是中序遍历顺序中紧邻在 p 前面的节点。
3. 示例：树 [2,1,3] 中序遍历为 [1,2,3]。
   • 节点 2 的前驱是 1。
   • 节点 1 是第一个节点，没有前驱。
   • 节点 3 的前驱是 2。

第二步：分析前驱节点的两种可能情况
假设我们要找节点 p 的前驱：

1. 情况一：p 有左子树。
   • 前驱是 p 左子树中的最大节点（即左子树的最右节点）。
   • 原因：中序遍历时，遍历完左子树的最大节点后，下一个就访问 p。
2. 情况二：p 没有左子树。
   • 前驱是 p 的祖先节点中，第一个“作为右子树的祖先”的父节点。
   • 更准确：从根向 p 走，记录最后一个“拐向右边”的节点。
   • 原因：如果 p 是父节点的右孩子，则父节点是前驱（因为父节点比 p 小，且中间没有其他节点）；如果 p 是父节点的左孩子，则继续向上找，直到某个节点是其父节点的右孩子（该父节点是前驱），如果直到根都没有，说明 p 是最小节点，无前驱。

第三步：用算法步骤描述
给定 BST 的根节点 root 和目标节点 p：

1. 如果 p.left != null：
   • 进入 p.left，一直向右走到尽头，返回该节点。
2. 否则（p.left == null）：
   • 从根开始遍历，用变量 pred 记录前驱（初始为 null）。
   • 比较当前节点 curr 与 p.val：
     • 如果 curr.val > p.val：p 在左子树，curr 不可能是前驱（因为比 p 大），移动到 curr.left。
     • 如果 curr.val < p.val：curr 可能是前驱（比 p 小），更新 pred = curr，然后移动到 curr.right。
     • 如果 curr == p：找到 p，结束循环，返回 pred。
3. 返回 pred。

第四步：举例演示
树结构（括号中为值）：

        6
       / \
      2   8
     / \
    1   4
       / \
      3   5

中序遍历：[1,2,3,4,5,6,8]。

例1：找节点 4 的前驱。

• 它有左子树（节点 3），进入左子树，一直向右：左子树根 3 无右子，所以前驱是 3。 ✅

例2：找节点 5 的前驱。

• 无左子树，从根开始：
  • 根 6 > 5，走左子 2。
  • 2 < 5，更新 pred = 2，走右子 4。
  • 4 < 5，更新 pred = 4，走右子 5。
  • 遇到 5，结束，返回 pred = 4。 ✅

例3：找节点 1 的前驱。

• 无左子树，从根开始：
  • 根 6 > 1，走左子 2。
  • 2 > 1，走左子 1。
  • 遇到 1，此时 pred 仍为初始 null，返回 null。 ✅

第五步：代码实现（迭代法）

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

def inorder_predecessor(root, p):
    # 情况1：p有左子树
    if p.left:
        curr = p.left
        while curr.right:
            curr = curr.right
        return curr
    
    # 情况2：p无左子树
    pred = None
    curr = root
    while curr != p:
        if curr.val < p.val:
            pred = curr
            curr = curr.right
        else:  # curr.val > p.val
            curr = curr.left
    return pred

时间复杂度：O(h)，h 是树高，最好 O(log n)（平衡时），最坏 O(n)（链状）。
空间复杂度：O(1)，只用了指针。

第六步：扩展思考

1. 如果 BST 节点有指向父节点的指针，可以从 p 向上找，代码会更简单。
2. 与“中序后继”对称，后继是右子树的最小节点，或无右子树时第一个“作为左子树的祖先”的父节点。
3. 在平衡 BST（如 AVL 树、红黑树）中，h = O(log n)，效率高。