最大值一定在最右路径末端、最小值一定在最左路径末端，因此可沿单支链o(h)直达，无需全树遍历；非递归实现更安全高效，空树返回nullptr，且必须严格区分left/right避免复制错误。
为什么直接遍历不是“极速”定位
二叉搜索树（BST）的性质决定了左子树所有节点值 小于 根，右子树所有节点值 大于 根。这意味着最大值一定在最右路径末端，最小值一定在最左路径末端——根本不需要中序遍历或 DFS 全树扫描。
常见错误是写成 findMin(root) 递归调用却没利用 BST 结构，比如误判空节点后仍继续递归，或忘记处理 root == nullptr 的边界；更隐蔽的问题是把 while 循环写成 if 判断，导致只走一层就返回。
- 时间复杂度必须是
O(h)（h 为树高），不是O(n) - 不能依赖额外容器（如 vector 存中序结果），否则失去“极速”意义
- 非递归实现更安全：避免深树导致栈溢出，也更容易看出路径走向
非递归找最小值：沿最左链一路向下
从根出发，只要当前节点有左孩子，就持续向左走；一旦左孩子为空，当前节点就是最小值。
TreeNode* findMin(TreeNode* root) {
if (!root) return nullptr;
while (root->left) {
root = root->left;
}
return root;
}
注意：root->left 是指针判空，不是 root->left != nullptr 冗余写法；若用递归，等价写法是 return root->left ? findMin(root->left) : root;，但递归深度不可控。
- 如果树退化成链表（全左倾），仍只需
O(n)时间，但这是最坏情况下的O(h)，符合预期 - 返回的是节点指针，不是值——便于后续删除或修改操作，别习惯性加
->val - 函数不修改树结构，可标
const TreeNode*参数，但需同步改内部逻辑（如用const TreeNode*类型变量）
非递归找最大值：沿最右链一路向下
逻辑完全对称：只要当前节点有右孩子，就持续向右走；右孩子为空时，当前节点即为最大值。
TreeNode* findMax(TreeNode* root) {
if (!root) return nullptr;
while (root->right) {
root = root->right;
}
return root;
}
和 findMin 唯一区别只有 left 换成 right。但容易错在复制粘贴后漏改——比如循环条件仍写 root->left，运行时可能崩溃或返回错误节点。
- 不要为了“复用”强行写一个通用函数传方向参数，会增加分支判断，反而降低缓存友好性
- 若树允许重复值且定义“最大值”为最右下节点（而非“最大键值的任意节点”），该实现依然正确
- 空树返回
nullptr是合理设计；调用方必须检查，否则解引用会 crash
实际使用时最容易被忽略的细节
这两个函数看似简单，但在真实项目里常因上下文环境出问题：比如在 AVL 或红黑树封装类中，findMin 被当成公有接口暴露，但内部节点指针类型是私有嵌套类，导致编译失败；或者在多线程环境下，没加锁就直接调用并缓存结果，而此时树正在被插入/删除修改。
- 如果 BST 带头结点（dummy head），起始点不是
root而是head->right，否则会把头结点当有效节点 - STL 中
std::set和std::map的begin()/rbegin()就是基于类似逻辑实现的，但底层用了更复杂的迭代器封装 - 没有“一键获取 min/max”的标准库函数——
std::min_element是线性扫描，不能替代
真正极速的关键不在代码行数，而在是否严格遵循 BST 的结构性质、是否规避了任何不必要的访问路径。写完立刻用退化树（单链）、空树、单节点树三类 case 测一下指针走向，比读十遍理论更管用。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
