二叉搜索树中节点的前驱是值严格小于其值的最大节点，左子树非空时为其左子树最右节点，否则为向上回溯中第一个右孩子为当前节点的祖先；带父指针可o(h)实现，无父指针需从根搜索并维护候选前驱。
前驱节点的定义和判断逻辑
二叉搜索树中，某个节点 node 的前驱是值严格小于 node->val 的最大节点。它要么在左子树的最右节点（左子树非空时），要么在向上回溯路径中第一个“右拐”进入当前子树的祖先（左子树为空时）。
关键点在于：不能只看父指针是否存在，而要看从根到该节点的路径上，最后一次向左走的位置——那个位置的父节点才是潜在前驱。
带父指针时的 O(h) 实现
如果每个节点有 parent 指针，查找前驱分两步：
- 若
node->left非空，前驱就是左子树中最右节点：循环访问right直到为空 - 若
node->left为空，则向上找第一个满足parent->right == node的祖先；找到后返回该parent，找不到则说明node是整棵树最小值，无前驱
示例代码片段：
TreeNode* predecessor(TreeNode* node) {
if (node->left) {
node = node->left;
while (node->right) node = node->right;
return node;
}
while (node->parent && node == node->parent->left)
node = node->parent;
return node->parent; // 可能为 nullptr
}
不带父指针时需从根开始搜索
没有 parent 指针时，无法回溯，必须从根出发模拟路径并记录可能的前驱候选。
核心思路：边向下走，边维护一个变量 pred，每当当前节点值 cur->val ，就更新 <code>pred = cur；然后根据比较结果决定往左还是右走。
- 这个方法适用于已知目标值
val查前驱，而不是给定节点指针 - 若必须基于节点指针（比如要删节点前找前驱），那不带父指针就只能先查值再重新搜索——时间复杂度仍是 O(h)，但实际多一次遍历
- 注意：不能直接用中序遍历数组索引减一，那不是 O(h)，而是 O(n)
容易被忽略的边界情况
写的时候常漏掉这些：
-
node是空指针或整棵树只有一个节点 → 前驱一定不存在 - 左子树存在但为空（即
node->left != nullptr但node->left->right全空）→ 最右节点就是node->left自身 - 向上回溯时
node->parent为nullptr还继续解引用 → 必须先判空 - 认为“左子节点就是前驱”——错，只有当该左子节点无右子树时才成立
真正麻烦的是：你得同时处理节点指针有效性、父子关系方向、以及“不存在前驱”的返回约定（通常返回 nullptr）。这几个条件混在一起，少一个判空就段错误。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
