题目描述

给定一个二叉树，确定它是否是一个完全二叉树。

Wikipedia 中对完全二叉树的定义如下：

若设二叉树的深度为 h，除第 h 层外，其它各层（1 到 h-1）的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1 到 $2^h$ 个节点。）

样例

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

输入：[1,2,3,4,5,null,7]
输出：false
解释：值为 7 的结点并不是尽可能地向左。

注意

• 树中有 1 到 100 个结点。

算法1

(深度优先遍历) $O(n)$

1. 首先通过一次深度优先遍历求出最大的深度 maxh。
2. 然后第二次深度优先遍历判断是否符合完全二叉树：当前结点深度若小于 maxh - 1 且它没有两个儿子，则直接返回 false；
3. 如果当前结点深度为 maxh - 1，则分为四种情况，有两个儿子；只有左儿子；只有右儿子；没有儿子；定义一个引用变量 vac 记录最后一层是否之前出现过空儿子的情况，根据 vac 的值和以上四种情况，不难判断是否为完全二叉树，以及更新 vac。具体细节参考代码。

时间复杂度

• 两次深度优先遍历，每次时间复杂度都是 $O(n)$，故总时间复杂度为 $O(n)$。

空间复杂度

• 深度优先遍历需要 $O(n)$ 的额外空间存储系统栈。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    int getHeight(TreeNode* rt) {
        if (rt == NULL)
            return -1;

        return max(getHeight(rt->left), getHeight(rt->right)) + 1;
    }

    bool check(TreeNode* rt, int h, int maxh, bool &vac) {
        if (h < maxh - 1) {
            if (!rt->left || !rt->right)
                return false;
        }
        else {
            if (!rt->left && !rt->right) {
                vac = true;
                return true;
            }
            else if (!rt->left && rt->right) {
                return false;
            }
            else if (rt->left && !rt->right) {
                if (vac == true)
                    return false;
                vac = true;
                return true;
            }
            else if (rt->left && rt->right) {
                if (vac == true)
                    return false;
                return true;
            }
        }

        if (rt)
            return check(rt->left, h + 1, maxh, vac) &&
                    check(rt->right, h + 1, maxh, vac);

        return false;
    }

public:
    bool isCompleteTree(TreeNode* root) {
        int maxh = getHeight(root);
        bool vac = false;
        return check(root, 0, maxh, vac);
    }
};

算法2

(层级遍历) $O(n)$

1. 我们仿照宽度优先遍历实现层级遍历。
2. 每层从左到右遍历时，判断如下条件：
   • 如果当前结点出现只有右儿子没有左儿子的情况，直接返回 false。
   • 如果当前结点有儿子结点，且当前层之前的结点出现了空缺 vac == true，或者且当前层必须为最后一层时 last_row == true，返回 false。
3. 每层从左到右遍历时，更新以下条件：
   • 如果当前结点没有儿子结点或者仅有左儿子结点，更新 vac 为 true。
   • 将左右儿子结点放入新队列。
4. 如果当前层遍历结束后，发现 vac == true，则说明下一层必须为最后一层，更新 last_row 为 true。

时间复杂度

• 每个结点仅遍历一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储队列。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);

        bool last_row = false;
        while (!q.empty()) {
            queue<TreeNode*> next_q;
            bool vac = false;

            while (!q.empty()) {
                TreeNode *u = q.front();
                q.pop();

                if (!u->left && u->right)
                    return false;

                if ((u->left || u->right) && (vac || last_row))
                    return false;

                if (!u->left || !u->right) vac = true;

                if (u->left) next_q.push(u->left);
                if (u->right) next_q.push(u->right);
            }

            if (vac) last_row = true;

            q = next_q;
        }

        return true;
    }
};

算法3

(宽度优先遍历) $O(n)$

1. 直接宽度优先遍历。
2. 遍历过程中，对于非空结点，我们将其左右儿子都入队（无论是否存在）。
3. 如果遍历时遇到了空结点，则说明从此时开始，接下来的所有结点都必须为空。

时间复杂度

• 每个结点仅遍历一次，最后一层结点会额外遍历两个空结点，但时间复杂度的仍然是 $O(n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储队列。

参考文献

• 鸣谢 @Aikin 提供思路。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            TreeNode *u = q.front();
            q.pop();

            if (u) {
                q.push(u->left);
                q.push(u->right);
            } else {
                while (!q.empty()) {
                    u = q.front();
                    q.pop();
                    if (u) return false;
                }

                return true;
            }
        }

        return false;
    }
};