递归中序遍历高效提取[low, high]区间节点值：遇node->valhigh则跳过右子树，仅在区间内才收集值并递归左右，避免全遍历。
如何用递归中序遍历高效提取 [low, high] 区间内的所有节点值
二叉搜索树（BST）的中序遍历天然有序，所以区间查询不必遍历整棵树——只要在递归过程中剪枝，就能避免无效访问。关键不是“怎么遍历”，而是“什么时候停、往哪边走”。
常见错误是写成先中序遍历全部节点再过滤：vector<int> result; inorder(root); then filter(result, low, high)</int>——这完全浪费了 BST 的结构优势，时间复杂度退化为 O(n)，且多一次遍历。
- 遇到
node->val ：左子树全小于 <code>low，直接跳过左递归，只查右子树 - 遇到
node->val > high：右子树全大于high，直接跳过右递归，只查左子树 - 只有
low val 时，才把 <code>node->val加入结果，并左右都递归
迭代写法下如何避免栈溢出并保持剪枝逻辑
递归虽简洁，但极端偏斜树（如链状 BST）可能导致栈溢出。迭代需手动维护栈，同时保留剪枝判断——不能简单套用通用中序迭代模板，否则会丢失区间优化。
核心是：入栈前就做范围判断，而不是出栈后再检查。例如，若当前节点值已大于 high，它的整个右子树都不该入栈；同理，小于 low 就不该入左子树。
- 初始化时只将
root入栈（如果非空） - 每次从栈顶取节点，先判断是否在区间内；若在，加入结果
- 决定是否 push 左/右子节点时，分别检查：
node->left是否可能含 ≥low的值（即node->left != nullptr && node->val > low），右子树同理 - 注意：仅靠
node->val > low不足以说明左子树有有效节点，必须结合 BST 性质——左子树最大值是node->val，所以只要node->val > low，左子树就「可能」含有效值，值得探索
std::set 或 std::map 能否替代手写 BST 区间查询？
可以，但要注意语义差异：std::set 底层是红黑树，支持 lower_bound(low) 和 upper_bound(high)，用迭代器区间构造结果 vector 是最简方案：
std::vector<int> rangeQuery(const std::set<int>& s, int low, int high) {
auto it1 = s.lower_bound(low);
auto it2 = s.upper_bound(high);
return std::vector<int>(it1, it2);
}</int></int></int>
但这不是“BST 的区间查询实现”，而是“用标准容器达成相同效果”。如果你需要自定义节点结构（比如带 parent 指针、存储子树大小）、或需在查询中附带修改（如删除匹配节点）、或面试要求手写逻辑，就不能依赖 std::set。
-
lower_bound返回首个 ≥low的元素，upper_bound返回首个 >high的元素——正好对应闭区间 [low, high] - 时间复杂度 O(log n + k)，k 是结果数量，和手写剪枝 BST 一致
- 但无法直接获取节点指针或执行树结构调整操作
为什么 findRange 返回 vector<int></int> 而不是 vector<treenode></treenode>？
返回原始值更安全、更常用。返回指针看似灵活，实则埋雷：调用方可能误存裸指针，在树被修改或析构后造成悬垂指针；而且多数场景只需数值（如统计、展示、导出），没必要暴露内部结构。
- 若真需节点引用（比如批量删除），应明确设计接口，如
void findRangeAndDelete(TreeNode*& root, int low, int high) - 返回
vector<int></int>也便于与 STL 算法配合（std::accumulate、std::sort等） - 性能上无差异——拷贝 int 成本远低于深拷贝节点，且现代编译器对小对象 vector 构造常做 RVO 优化
真正容易被忽略的是边界处理：low 和 high 可能不存在于树中，lower_bound 和递归剪枝都必须兼容这种情况；另外，整数溢出（如 low = INT_MIN）会让 node->val 判断失效——实际中应使用 <code>long long 或加 guard 条件。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
