前驱节点是BST中比目标节点小的最大节点；有左子树时为其左子树最右节点，无左子树时需向上回溯首个作为右子节点的祖先，无则不存在。
前驱节点是什么，为什么不能只靠左子树最大值
在 BST 中，某个节点的前驱是比它小的最大节点。很多人第一反应是“往左走到底再往右”，但这是错的——如果目标节点没有左子树，前驱根本不在左子树里，而是在向上回溯路径中某个祖先节点上。比如节点 15 的左子树为空，它的前驱是父节点 10（假设结构为 10→right=15），这时必须沿父指针向上找第一个“被右子树访问过”的祖先。
带 parent 指针的查找逻辑怎么写才不漏情况
有 parent 指针时，分两种主路径：
- 若节点有左子树：前驱就是左子树中的最右节点（即
left→right→right→…直到right == nullptr） - 若节点无左子树：从当前节点开始向上遍历
parent，直到遇到第一个满足node == parent->right的祖先，该祖先就是前驱；如果一路上都是node == parent->left，说明当前节点是最小值，无前驱
注意：parent 指针必须在插入/构造时正确维护，否则向上遍历会崩溃或逻辑错乱。
不带 parent 指针时如何用递归模拟回溯路径
没有 parent 就得靠递归隐式栈“记住来路”。核心是传入一个候选前驱变量（如 TreeNode* prev），并在中序遍历过程中更新它：
立即学习“C++免费学习笔记（深入）”；
TreeNode* findPredecessor(TreeNode* root, int target, TreeNode*& prev) {
if (!root) return nullptr;
if (root->val == target) return prev; // 找到目标，返回当前记录的前一个
if (target < root->val) {
return findPredecessor(root->left, target, prev);
} else {
prev = root; // 当前节点比 target 小，可能是候选
return findPredecessor(root->right, target, prev);
}
}这个写法本质是“边搜索边记最后一个小于 target 的节点”，不依赖子树结构，但要求调用前将 prev 初始化为 nullptr。容易漏掉的点是：没处理 target 不在树中的情况，此时返回的 prev 是小于它的最大存在节点（不是错误，但需明确语义）。
迭代写法中 stack 存什么、什么时候更新前驱
用栈模拟中序遍历找前驱时，关键不是存所有路径，而是只在向右走之前记录“可能的前驱”：
- 一路向左压栈，不更新前驱
- 每次从栈弹出一个节点
cur，它是当前子树的最小值；如果cur->val ，它就是截至目前最接近的前驱候选，更新 <code>prev = cur - 然后转向
cur->right继续搜索；一旦cur->val >= target，说明已越过目标，不再更新prev，直接 break
这种迭代方式空间复杂度 O(h)，但容易在边界判断上出错——比如把 >= 写成 >，就会让等于 target 的节点也被当作候选，导致返回自身。
真正难的不是写对某一种情况，而是统一覆盖“节点存在/不存在”“有无左子树”“是否为根”这三类组合；多数 bug 出在向上回溯时没判空 parent，或者递归中忘记传递引用参数。
