一、 什么是完全二叉樹

1.1 定義

一棵深度為k的有n個結(jié)點的二叉樹，對樹中的結(jié)點按從上至下、從左到右的順序進行編號，如果編號為i（1≤i≤n）的結(jié)點與滿二叉樹中編號為i的結(jié)點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。

1.2 完全二叉樹判定

1. 使用中序遍歷二叉樹，生成一個LinkedList集合隊列
2. 每次彈出一個節(jié)點，根據(jù)該節(jié)點獲取左右子樹節(jié)點
3. 如果左數(shù)為空，右樹不為空，其不是一個完全二叉樹
4. 如果遇到了不雙全的節(jié)點之后，又發(fā)現(xiàn)當(dāng)前節(jié)點不是葉節(jié)點，其不是一個完全二叉樹

二、源碼

  public static boolean isCB1(Node head) {
        if (head == null) {
            return true;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        boolean flag = false;
        while (!queue.isEmpty()) {
            head = queue.poll();
            Node left = head.left;
            Node right = head.right;
            if (
                    (flag && (left != null || right != null)) || (left == null && right != null)
            ) {
            }
            if (left != null) {
                queue.add(left);
            }
            if (right != null) {
                queue.add(right);
            }
            if (left == null || right == null) {
                flag = true;
            }
        }
        return flag;
    }