【2024考研】题解24 | #判断是不是完全二叉树#

#include <queue>
class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        // write code here special case
        if (root == NULL) {
            return true;
        }
        queue<TreeNode *> q;
        q.push(root);
        TreeNode *now;
        //层序遍历呗也不用输出
        bool flag = false;
        while(!q.empty()){
            //没有暂存行数组
            int n = q.size();
            for(int i = 0; i < n; i++){
                now = q.front();
                //没有行数组pushback
                q.pop();
                if (now == NULL) {
                    flag = true;
                }
                else{
                    if(flag) return false;
                    q.push(now->left);
                    q.push(now->right);
                }
            }
            //没有输出
        }
        return true;
    }
};

基于层序遍历：

#include <queue>
#include <vector>
class Solution {
public:
    vector<vector<int> > levelOrder(TreeNode* root) {
        // write code here
        //二维数组存储
        vector<vector<int>> ans;
        //特例 空
        if(root == nullptr) return ans;
        //构造辅助队列q 根放进来
        queue<TreeNode*> q;
        q.push(root);
        //树节点指针定位当前节点
        TreeNode* cur;
        //只要队列里边不空 猛猛干
        while (!q.empty()) {
            vector<int> row;//临时行数组存储单层结点
            int n = q.size();//每层长度随着每一次循环而临时确定

            for(int i = 0; i < n; i++){
                cur = q.front();//当前结点指针定位到队头
                row.push_back(cur->val);//行数组暂时存储该节点值
                q.pop();//取值后的节点出队

                if(cur->left) q.push(cur->left);//注意这里不是递归
                if(cur->right) q.push(cur->right);
            }
            ans.push_back(row);//临时存储row传给最终ans输出
        }
        return ans;//最终输出
    }
};

算法基本思想：

- 使用层序遍历的方式判断一棵二叉树是否是完全二叉树。

- 首先判断特殊情况，如果根节点为空，则返回true。

- 使用队列存储节点，将根节点入队。

- 定义一个标志位flag，用于判断是否出现了空节点。

- 进入循环，循环条件为队列不为空：

- 获取当前层的节点个数n。

- 遍历当前层的节点，将节点依次出队，判断是否为空：

- 如果节点为空，将flag标志位置为true。

- 如果节点不为空：

- 如果flag标志位为true，说明之前已经出现了空节点，当前节点不为空，则不是完全二叉树，返回false。

- 将当前节点的左右子节点入队。

- 循环结束后，如果flag标志位为true，则说明已经出现了空节点，返回false。

- 返回true，说明是完全二叉树。

时间复杂度：

O(n)，其中n是二叉树的节点个数。需要遍历每个节点一次。

空间复杂度：

O(n)，队列的大小最大为二叉树的宽度，最坏情况下，二叉树是一个满二叉树，宽度为n/2，因此空间复杂度是O(n)。