LeetCode 958. 二叉树的完全性检验

958. 二叉树的完全性检验

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

在一个 完全二叉树 中，除了最后一个关卡外，所有关卡都是完全被填满的，并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2h 节点之间的最后一级 h 。

广度优先遍历，遇到第一个没有两个儿子的节点之后（这个节点不能有右儿子），每个节点都不能有儿子

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        queue<TreeNode*> q;
        q.push(root);
        bool check(false);
        while (q.size()) {
            int k = q.size();
            for (int i = 0; i < k; ++i) {
                auto front = q.front();
                q.pop();
                if (!check) {
                    if (front->left && front->right) {
                        q.push(front->left);
                        q.push(front->right);
                    } else if (front->right) {
                        return false;
                    } else {
                        if (front->left) {
                            q.push(front->left);
                        }
                        check = true;
                    }
                } else {
                    if (front->left || front->right) {
                        return false;
                    }
                }
                
            }
        }
        return true;
    }
};

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