满二叉树、完全二叉树和完美二叉树有什么区别？

简化版

满二叉树强调每个节点要么 0 个孩子、要么 2 个孩子；完全二叉树强调最后一层从左到右填充，适合数组存储堆；完美二叉树强调所有内部节点都有 2 个孩子且所有叶子在同一层。

详细版

这三个概念很容易混，但关注点不同：

• 满二叉树：节点度数只能是 0 或 2，不能只有一个孩子。
• 完全二叉树：除最后一层外都满，最后一层从左到右连续填充。
• 完美二叉树：所有层都满，叶子节点深度完全相同。

完美二叉树一定是完全二叉树，也一定是满二叉树；但满二叉树不一定完全，完全二叉树也不一定满。面试里要用反例说明：一个根节点只有左孩子是完全二叉树，但不是满二叉树。

完整版教学

一、为什么这些名字容易混

中文里“满”“完全”“完美”听起来都像“很满”，但它们来自不同判定角度。满二叉树看的是每个节点的孩子数量，完全二叉树看的是层序填充形态，完美二叉树看的是整棵树每一层是否都填满。

可以先把关注点拆开：

满：节点局部，孩子数只能是 0 或 2
完全：整体形状，按层从左到右不能有空洞
完美：每层都满，叶子同深度

一旦把“节点局部”和“整体层次”分开，就不容易把它们混成一个概念。

二、满二叉树到底满在哪里

满二叉树的英文常对应 full binary tree。它要求每个节点要么没有孩子，要么左右孩子都有。它不要求所有叶子在同一层。

例如：

    1
   / \
  2   3
     / \
    4   5

这棵树是满二叉树，因为节点 1、3 都有两个孩子，节点 2、4、5 都没有孩子。但它不是完美二叉树，因为叶子 2 在第 2 层，叶子 4、5 在第 3 层。

三、完全二叉树为什么适合堆

完全二叉树要求除最后一层外都填满，最后一层从左到右连续。这个性质让它可以紧凑地放进数组。

        1
      /   \
     2     3
    / \   /
   4   5 6

数组表示是 [1,2,3,4,5,6]，没有中间空洞。对于下标 i，左孩子可以用 2*i+1，右孩子用 2*i+2。这就是堆结构依赖完全二叉树的原因。

四、完美二叉树为什么最严格

完美二叉树要求所有内部节点都有两个孩子，并且所有叶子都在同一层。高度为 h 的完美二叉树节点数有固定公式。

节点数 = 2^(h+1) - 1
叶子数 = 2^h

如果高度按根为 0 计算，高度 2 的完美二叉树有 2^3 - 1 = 7 个节点。这种结构最规整，但真实数据里并不总能保持。

五、三者之间的包含关系

完美二叉树一定满足满二叉树，因为所有内部节点都有两个孩子；也一定满足完全二叉树，因为每一层都填满。反过来都不成立。

类型	局部孩子数	最后一层要求	叶子同层
满二叉树	0 或 2	不要求	不要求
完全二叉树	可有单左孩子	从左到右填充	不要求
完美二叉树	0 或 2	全部填满	要求

记住这个表，比死背定义更可靠。

六、面试中怎么构造反例

完全但不满：根节点只有左孩子，这满足最后一层从左到右填充，但根只有一个孩子，所以不满。满但不完全：前面例子中叶子层不靠左连续填满，就不完全。

记忆钩子：满看“每个节点有没有独生子”，完全看“层序有没有空洞”，完美看“每层是不是全满”。

七、常见误区与追问

• 误区：满二叉树就是所有层都满。 这是完美二叉树的要求，满二叉树只限制节点孩子数。
• 误区：完全二叉树不能有单孩子节点。 可以有，但只能是最后一层附近的单左孩子，不能有单右孩子。
• 误区：完美二叉树和完全二叉树一样。 完美更严格，完全只要求最后一层靠左。
• 追问：堆为什么用完全二叉树？ 因为完全二叉树能用数组紧凑存储，父子下标可由公式计算。
• 追问：完美二叉树节点数公式是什么？ 高度 h 从 0 开始时，节点数是 2^(h+1)-1。

八、加强记忆

这三个概念可以按严格程度记：完美最严格，既全满又同层；完全关注层序靠左，服务数组存储；满关注局部孩子数，不能有独生子。面试时配一个反例，基本就能把区别讲清楚。