构建二叉搜索树
哪些公司问过
答案要点
- BST 性质:左子树值都小于根,右子树值都大于根,中序遍历有序
- 插入:从根比较,小往左、大往右,到空位置新建节点;递归或迭代实现
- 重复值需约定处理:忽略、计数或统一放到一侧
- 单次插入 O(h),随机输入约 O(n log n),有序输入退化为 O(n²)
- 有序数组取中点递归建树可得平衡 BST;需持续平衡用 AVL 或红黑树
易错点
- 只保证父子关系满足大小,误以为就是 BST
- 忽略有序输入导致树退化成链表
- 递归插入时没把返回的新节点接回父节点
面试官常见追问
- BST 删除节点怎么做?
- 怎么验证一棵树是 BST?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场