二叉树的完全性检验

发表于 阅读次数：

题目

leetcode-958题，给定一个二叉树，确定它是否是一个完全二叉树(最后一层前的每一层都是满的，最后一层都往左靠)。

正确

错误

例子如下：

1
2
3
4
输入：[1,2,3,4,5,6]
输出：true
解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），
且最后一层中的所有结点（{4,5,6}）都尽可能地向左。

思路

我们因为完全二叉树，除了最后一层前每一层都是满的，所以我们可以用层序遍历。我们在层序遍历的基础上划分两种情况：

来看下具体的例子：

  • 情况1

  • 情况2

接下来看下具体的实现吧。

实现

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
public static boolean isCBT(TreeNode head) {

        if(head != null) {
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(head);
            boolean flag = false;
            TreeNode l ;
            TreeNode r;
            while(!queue.isEmpty()) {

                head = queue.poll();
                l = head.left;
                r = head.right;
                //(flag && (l != null || r != null))表示case1的情况下后续的节点不是叶节点
                //(l == null && r != null)表示case2
                if((flag && (l != null || r != null)) || (l == null && r != null)) {
                    return false;
                }

                if(head.left != null) {
                    queue.offer(head.left);
                }
                if(head.right != null) {
                    queue.offer(head.right);
                }else {
                    //是否要判断case1
                    flag = true;
                }
            }
        }
        return true;
    }