GESP 六级 · GESP 202509 C++ 六级 第 23 题

下面代码实现的二叉排序树的查找操作时间复杂度为 $O(h)$，其中 $h$ 为树高。

TreeNode* searchBST(TreeNode* root, int val) {
    while (root && root->val != val) {
        root = (val < root->val) ? root->left : root->right;
    }
    return root;
}

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】二叉树｜时间复杂度分析｜树高

1. 🎯 考纲定位

本题考查《GESP 六级 数据结构模块》中"二叉树"章节的核心概念。命题人把这道题放在这里，就是要卡住那些只会背"二叉搜索树查找是 O(log n)"的考生——六级考生最常犯的错误就是把平衡二叉树的性质默认套用到普通二叉排序树上。树高 h 的范围是 1 到 n，只有当树完全平衡时才取到 log n，命题人用"二叉排序树"这个宽泛定义，就是要测试你是否区分了 BST 和 AVL/B-S 树。