bst中直接遍历全树找最值低效，因其违背o(h)设计初衷；正确做法是沿最左/最右路径直达，时间复杂度为o(h)，退化时h=n才变为o(n)。
为什么直接遍历找最大/最小节点是低效的
在未做任何优化的二叉搜索树（BST）中，find_max 或 find_min 如果靠递归或迭代遍历全树，时间复杂度会退化到 O(n)——这完全违背了 BST 的设计初衷。BST 的核心优势在于利用左子树
如何用 O(h) 时间找到 min/max 节点
最小值一定在最左端叶子（或最左非空节点），最大值一定在最右端。不需要比较键值，也不需要回溯：
-
find_min：从根开始，不断走left指针，直到left == nullptr -
find_max：从根开始，不断走right指针，直到right == nullptr - 高度
h决定实际耗时：平衡树是O(log n)，退化成链表则为O(n)
示例（非递归实现）：
TreeNode* find_min(TreeNode* root) {
if (!root) return nullptr;
while (root->left) root = root->left;
return root;
}
<p>TreeNode<em> find_max(TreeNode</em> root) {
if (!root) return nullptr;
while (root->right) root = root->right;
return root;
}</p>
插入/删除后是否需要更新极值缓存
极值节点本身不参与 BST 的结构维护逻辑，所以 insert 和 delete 后无需“更新”极值——下次调用 find_min/find_max 仍可直接走最左/最右路径。但要注意：
- 如果树为空，两次调用都返回
nullptr，需判空处理 - 若频繁查询极值（如实现有序集合的
begin()/end()），可考虑在树结构中缓存指针，但会增加插入/删除的维护成本 - 缓存仅在单线程场景下安全；多线程中若无同步，缓存可能失效，不如每次实时查
std::set/std::map 里怎么拿到 min/max 元素
标准库容器底层通常是红黑树，已按 BST 性质组织，但不暴露节点指针。获取极值的方式与手写 BST 不同：
- 最小元素：
*s.begin()（s是std::set） - 最大元素：
*s.rbegin()或*prev(s.end()) -
begin()和rbegin()均为常数时间操作，因为红黑树内部维护了指向最左/最右节点的指针 - 不要试图用
std::min_element(s.begin(), s.end())——那是O(n)，纯属浪费
极值定位的关键从来不是“怎么写循环”，而是意识到它本就不该遍历整棵树。真正容易被忽略的，是当树深度很大（比如插入序列接近单调）时，O(h) 和 O(n) 实际表现几乎没区别——这时候得考虑是否真需要 BST，还是换用跳表、有序数组加二分更合适。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
