一道面试高频题-如何判断完全二叉树

在这里插入图片描述

解题思路

用一个队列按层遍历所有节点，同时检测2个关键条件：

1.不能出现"有右无左"

如果某个节点只有右孩子没有左孩子，直接判定为非完全二叉树。

1
2
3
4
5


     1
    / \
   2   3
    \      ← 节点2只有右孩子，违规！
     5

2.遇到"不双全"节点后，后续必须都是叶子节点

一旦遇到左右孩子不双全的节点（只有左孩子或两个都没有），那么后面的所有节点都必须是叶子节点。

1
2
3
4
5


     1
    / \
   2   3
  /         ← 节点2只有左孩子，后面的节点3必须是叶子
 4

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


public static int MAXN = 101;
public static TreeNode[] queue = new TreeNode[MAXN];
public static int l, r;  // l是队头指针，r是队尾指针

public static boolean isCompleteTree(TreeNode h) {
    if (h == null) {
        return true;  // 空树认为是完全二叉树
    }
    
    // 初始化队列
    l = r = 0;
    queue[r++] = h;
    
    // leaf标记：是否遇到过"不双全"的节点
    boolean leaf = false;
    
    while (l < r) {
        h = queue[l++];  // 出队
        
        // 两种违规情况
        if ((h.left == null && h.right != null) ||  // 情况1：有右无左
            (leaf && (h.left != null || h.right != null))) {  // 情况2：遇到leaf标记后还有孩子
            return false;
        }
        
        // 左孩子入队
        if (h.left != null) {
            queue[r++] = h.left;
        }
        
        // 右孩子入队
        if (h.right != null) {
            queue[r++] = h.right;
        }
        
        // 如果当前节点不双全，标记leaf
        if (h.left == null || h.right == null) {
            leaf = true;
        }
    }
    
    return true;
}

如果觉得有帮助，欢迎点赞、关注、转发~