二叉树中最大的二叉搜索子树
哪些公司问过
答案要点
- 后序遍历,每个节点返回:是否 BST、节点数、最小值、最大值
- 判定条件:左右都是 BST,且左子树最大值 < 根 < 右子树最小值
- 是 BST 时合并大小和最值,并更新全局最大值
- 空树返回 BST、大小 0、最小值 +∞、最大值 -∞,简化叶子判断
- 时间 O(n),空间 O(h);自顶向下逐个验证会退化为 O(n²)
易错点
- 只比较节点和左右孩子的值,忽略整棵子树的最值约束
- 不是 BST 时仍然向上累加大小
- 空节点最值哨兵设置反了,导致叶子节点判定失败
面试官常见追问
- 如果要返回最大 BST 子树的根节点怎么改?
- 节点值可能是整型最大最小值时怎么处理?
- 如何验证一棵树是否为 BST?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场