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

958. 二叉树的完全性检验

显示英文描述

用户通过次数119
用户尝试次数157
通过次数123
提交次数378
题目难度Medium

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

百度百科中对完全二叉树的定义如下：

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

示例 1：

输入：[1,2,3,4,5,6]

输出：true

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

示例 2：

输入：[1,2,3,4,5,null,7]

输出：false

解释：值为 7 的结点没有尽可能靠向左侧。

提示：

树中将会有 1 到 100 个结点。

/**

 * 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) {

        queue<TreeNode*>que;

        que.push(root);

        int flag = ;   //flag == 0 表示到最后一个节点了，再也不能往队列里加节点了。

        while(!que.empty()){

            TreeNode* t = que.front();que.pop();

            if(flag == ){

                if(t->left == NULL && t->right != NULL) return false;  //题中情况

                if(t->left == NULL || t->right == NULL) flag = ;

                if(t->left) que.push(t->left);

                if(t->right) que.push(t->right);

            }

            else{

                if(t->left != NULL||t->right != NULL)return false;

            }

        }

        return true;

    }

};

————今天脑子有点不好使，贼傻逼。

巴特西

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

958. 二叉树的完全性检验

最新文章

热门文章