前驱节点是中序遍历中位于目标节点之前的节点；有左子树时为其左子树最右节点，无左子树时需沿父指针向上回溯至首个为右孩子的祖先，否则不存在。
前驱节点是什么，为什么不能直接找左子树最大值
前驱节点是中序遍历中位于目标节点之前的那个节点。很多人第一反应是“找左子树的最右节点”，但这只在目标节点有左子树时成立；如果 node->left 为空，前驱必须向上回溯——从父节点一路往回找，直到当前节点是某个祖先的右子树分支为止。
典型错误是忽略无左子树的情况，导致返回空指针或崩溃。比如查询根节点且它没有左孩子时，前驱根本不存在，但代码若硬找 left->right 就会解引用空指针。
带父指针的BST如何安全查前驱
如果有 parent 指针（如自己实现的节点结构含 TreeNode* parent），逻辑清晰且不易出错：
- 若
node->left非空：一路向右走到left->right->right...直到right == nullptr - 若
node->left为空：沿parent向上，跳过所有“是父节点左孩子的路径”，第一个满足node == parent->right的parent就是前驱 - 如果一路上升到根都没遇到
node == parent->right，说明目标节点是整棵树最小值，无前驱
示例片段（假设节点结构含 parent）：
TreeNode* inorderPredecessor(TreeNode* node) {
if (!node) return nullptr;
if (node->left) {
TreeNode* p = node->left;
while (p->right) p = p->right;
return p;
}
while (node->parent && node == node->parent->left)
node = node->parent;
return node->parent; // 可能为 nullptr
}
不带父指针时怎么查——必须从根开始模拟中序路径
没有 parent 指针时，不能“向上走”，只能从根出发，边遍历边记录可能的前驱候选。核心思路是：在查找目标节点的过程中，每当向右走，就更新前驱候选为当前节点；向左走则不更新。
这是因为中序遍历时，所有“当前节点的左子树已遍历完、正要进右子树”的时刻，当前节点就是即将访问的右子树中所有节点的前驱候选。
- 初始化
pred = nullptr - 从
root开始搜索目标node值（注意：这里按值查，不是按指针地址；若需按指针查，得额外标记路径） - 每次
cur->val ：说明目标在右子树，pred = cur，然后cur = cur->right - 每次
cur->val >= target：往左走，cur = cur->left（不更新pred） - 找到目标后，
pred就是其前驱；没找到则返回nullptr
这个方法依赖值比较，不适用于仅凭指针地址判断的场景——比如多个节点值相同，你只想找特定内存地址节点的前驱，那就必须用带父指针的方式或额外维护路径栈。
容易被忽略的边界和性能点
实际写的时候最容易漏掉三点：
-
node为nullptr或树为空时未判空，直接解引用 - 在无左子树情况下，上升过程中忘记检查
node->parent == nullptr就继续访问node->parent->left，造成越界 - 使用值查找法时，没处理重复值：BST允许重复值插入右子树（或左，取决于实现），但前驱定义基于中序序列位置，而非值大小，所以严格来说应按节点在中序序列中的物理位置定前驱，而非值关系
如果BST节点值不唯一，或者你需要精确对应某个指针地址节点的前驱，带父指针 + 路径回溯是唯一可靠方式。值查找法看起来简洁，但隐含了“所有节点值唯一”且“你查的是值而非实例”的前提。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
