判断一棵二叉树是否为满二叉树
哪些公司问过
答案要点
- 先确认定义:国内指每层全满,国际 full binary tree 指每个节点 0 或 2 个孩子
- 每层全满:节点数 n 与高度 h 满足 n=2^h−1
- 或递归判断左右子树都满且高度相等
- 0 或 2 个孩子定义:只有一个孩子即返回假,否则递归左右子树
- 时间 O(n),空间 O(h),空树和单节点通常视为满
易错点
- 不确认定义就直接写代码
- 用 2^h 计算时高度从 0 还是从 1 开始搞错
- 只检查根节点的两个孩子,没有递归检查子树
面试官常见追问
- 如何判断完全二叉树?
- 满二叉树中叶子节点数和度为 2 的节点数有什么关系?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场