判断二叉树是否为二叉搜索树
哪些公司问过
答案要点
- BST:左子树都小于根,右子树都大于根,子树也是 BST
- 中序遍历法:结果必须严格递增,记录前一个值比较
- 递归上下界法:每个节点值必须落在 (下界, 上界) 开区间内
- 只比较节点与左右孩子会漏掉跨层的违反,需带上祖先的约束
- 时间 O(n),空间 O(h);确认是否允许重复值,边界:空树、单节点
易错点
- 只比较节点和左右孩子
- 用 int 最值作边界,遇到极端值误判
- 允许相等值却没有和面试官确认
- 中序遍历用大于等于判断,忽略重复值
面试官常见追问
- 为什么不能只比较节点和左右孩子?
- 上下界的值用 int 会有什么问题?
- 用中序遍历有什么需要注意?
- 普通二叉树和二叉搜索树的区别是什么?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场