欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 958 二叉树的完全性检验(超简洁写法)

程序员文章站 2022-07-15 11:16:30
...

题目描述

leetcode 958 二叉树的完全性检验(超简洁写法)

思路

利用queue进行广度优先遍历。

出队列时,如果遇到空值,则跳出,如果此时队列还有值,那么此数不是完全二叉树

1 2 3 4 5 null 7 这是广度优先遍历 7 不少完全二叉树

1 2 3 4 5 6 null 实例一为完全二叉树

代码

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        queue <TreeNode *> bfs;
        bfs.push(root);
        while(!bfs.empty())
        {
            TreeNode* temp = bfs.front();
            bfs.pop();
            if(temp == NULL)
                break;
            bfs.push(temp->left);
            bfs.push(temp->right);
        }
        while(!bfs.empty())
        {
            TreeNode* temp = bfs.front();
            if(temp!=NULL)
                break;
            bfs.pop();
        }
        return bfs.empty();
    }
};

复杂度分析

坏的情况所有节点需要遍历一次时间O(n);空间O(n);

重难点分析

树的广度优先遍历方式,利用队列进行广度优先遍历。

扩展思路:利用flag记录是否遇到空值