958. 二叉树的完全性检验
程序员文章站
2022-07-15 11:16:54
...
958. 二叉树的完全性检验
1.题目描述
给定一个二叉树,确定它是否是一个完全二叉树。
百度百科中对完全二叉树的定义如下:
若设二叉树的深度为 h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。(注:第 h 层可能包含 1~ 2h 个节点。)
示例 1:
示例 2:
提示:
1.树中将会有 1 到 100 个结点。
2.思路
观察下面的图片,图中箭头的顺序,就是层次遍历的顺序。将所有节点排成一列,包括缺失的null节点。null节点之后必须全部是null节点。否则,就不是完全二叉树。
例如:
节点排成一列后,1,2,3,4,5,6,null.是完全二叉树。
节点排成一列后, 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 15.三数之和
推荐阅读
-
LeetCode第958题 二叉树的完全性检验
-
958. 二叉树的完全性检验
-
Leetcode刷题记录——958. 二叉树的完全性检验
-
leetcode 第 958 题:二叉树的完全性检验(C++)
-
leetcode 958 二叉树的完全性检验(超简洁写法)
-
leetcode 958. 二叉树的完全性检验(输出是否是完全二叉树 dfs/bfs每次假如队列的时候判断 值是不是sz)
-
给定两个非空二叉树 s 和 t,检验s 中是否包含和 t 具有相同结构和节点值的子树
-
二叉树的完全性检验——Python实现(BFS)
-
272、二叉树的完全性检验
-
给定两个非空二叉树 s 和 t,检验s 中是否包含和 t 具有相同结构和节点值的子树