958. Check Completeness of a Binary Tree
Medium

Given a binary tree, determine if it is a complete binary tree.

Definition of a complete binary tree from Baike:
  In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example 1:

测试用例1
1
2
3
Input: [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

Example 2:

测试用例2
1
2
3
Input: [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.

Note:

1
1.The tree will have between 1 and 100 nodes.

  算法思想:看到这个题目,比较容易想到的也许就是层序遍历来判断了。即采用层序遍历的方式遍历结点,如果当前结点是空的,则判断队列里是否还有结点,即该结点之后是否还有结点。如果有,则不是完全二叉树。如果没有,则继续判断直至遍历完所有结点。


Javascript Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/

var isCompleteTree = function(root) {
if(root === null) return true //如果是空树,也是完全二叉树
let queue = [root]
while(queue.length != 0){ //层序遍历
let p = queue.shift()
if(p){ //区别正常层序遍历判空左右,不判空左右孩子直接进队列
queue.push(p.left)
queue.push(p.right)
}
else{ //如果当前结点为空,则将队列剩下元素全部弹出,如果非空,则不是完全二叉树。
while(queue.length != 0){
let pson = queue.shift()
if(pson)
return false
}
}
}
return true //如果为空,跳出循环并返回是完全二叉树
};

C Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/

bool isCompleteTree(struct TreeNode* root){
if(root == NULL) return true; //如果为空树,则返回是完全二叉树
int front = -1, rear = -1;
struct TreeNode *queue[1000]; //c语言没有变长数组,恰巧题目有给出结点在1-100,定1000比较过分的,最好比最大限制多10即可。
queue[++rear] = root; //根结点入队
while( front < rear ){
struct TreeNode *p = queue[++front]; //队首出队
if(p!=NULL){ //下面过程同javascript解法
queue[++rear] = p->left;
queue[++rear] = p->right;
}
else{
while( front < rear ){
struct TreeNode *q = queue[++front];
if(q!=NULL)
return false;
}
}
}
return true;
}

本文标题:判断完全二叉树

文章作者:JarryChen

发布时间:2019年10月26日 - 08:05

最后更新: 2020年01月07日 20:17

原始链接: https://jarrychen.xyz/archives/d3eeae64.html

× 请我喝奶茶~
打赏二维码