不能直接从子节点反向找父节点，因为标准二叉树节点无 parent 指针；实用解法是在 dfs 时向下传递父指针，命中即返，并处理根节点无父的边界情况。
为什么不能直接从子节点反向找父节点
因为标准二叉树节点结构（如 struct TreeNode { int val; TreeNode* left; TreeNode* right; };）不包含 parent 指针。除非你事先在建树时手动维护双向链接，否则运行时无法从任意 TreeNode* 逆向定位其父节点。
最实用的解法：递归遍历时记录父节点
核心思路是「向下传递父指针」，而不是向上查找。在 DFS 过程中，每访问一个子节点，就把当前节点作为它的父节点传下去。这样一旦命中目标值，就能立刻返回父指针。
常见错误是写成“找到目标后再回溯找父”，这不仅逻辑复杂，还容易漏掉根节点无父的情况。
- 必须处理目标节点是根节点的情形——此时应返回
nullptr - 递归函数需接受额外参数
TreeNode* parent，初始调用传nullptr - 不要在左右子树都递归后才判断结果；命中即返，避免多余遍历
示例代码片段：
TreeNode* findParent(TreeNode* root, int target) {
if (!root) return nullptr;
if (root->left && root->left->val == target) return root;
if (root->right && root->right->val == target) return root;
TreeNode* p = findParent(root->left, target);
if (p) return p;
return findParent(root->right, target);
}
如果需要频繁查父节点，该重构树结构吗
查一次就遍历一遍，时间复杂度 O(n)，对小树没问题；但若需多次查询（比如实现 BST 的删除操作），重复遍历代价高。这时值得考虑改造节点定义：
- 添加
TreeNode* parent;成员，并在插入/构建时严格维护 - 注意：所有修改树结构的操作（插入、旋转、删除）都必须同步更新
parent指针，否则后续查询会出错 - STL 容器（如
std::set）内部不暴露节点指针，也无法获取父节点——别试图 cast 或 hack 内部实现
BST 特性在这里能优化查找吗
不能。父节点位置与 BST 的有序性无关——它只取决于插入路径和树形结构。即使你知道目标值比根小，也不能跳过右子树去查父节点，因为父节点可能在任意层级上。BST 性质只对查找、插入、中序遍历有用，对「父子关系定位」没有加速作用。
真正影响性能的是树高：平衡 BST（如 AVL、红黑树）能让最坏查找降到 O(log n)，但前提是你的树真保持了平衡，且你有办法拿到每个节点的父指针——而这又回到前面的结构改造问题。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
