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

958. 二叉树的完全性检验

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

958. 二叉树的完全性检验

1.题目描述

给定一个二叉树,确定它是否是一个完全二叉树。
百度百科中对完全二叉树的定义如下:

若设二叉树的深度为 h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。(注:第 h 层可能包含 1~ 2h 个节点。)
示例 1:
958. 二叉树的完全性检验
示例 2:
958. 二叉树的完全性检验
提示:
1.树中将会有 1 到 100 个结点。

2.思路

  观察下面的图片,图中箭头的顺序,就是层次遍历的顺序。将所有节点排成一列,包括缺失的null节点。null节点之后必须全部是null节点。否则,就不是完全二叉树。
例如:
958. 二叉树的完全性检验
节点排成一列后,1,2,3,4,5,6,null.是完全二叉树。
958. 二叉树的完全性检验
节点排成一列后, 1,2,3,4,5,null,7.null后有了节点7。不是完全二叉树。

3.代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        if(root == NULL){
            return true;
        }
        queue<TreeNode*> q;
        q.push(root);
        bool isNULL = false;//之后的节点是否出行NULL
        while(!q.empty()){
            TreeNode* node = q.front();
            q.pop();
            if(node != NULL){
                if(isNULL){
                    return false;
                }
                q.push(node->left);
                q.push(node->right);
            }
            else{
                isNULL = true;
            }
        }
        return true;
    }
};

4.复杂度分析

时间复杂度:O(n)
空间复杂度:O(n)

相关标签: LeetCode树专题