题解 | #判断是不是完全二叉树#
判断是不是完全二叉树
https://www.nowcoder.com/practice/8daa4dff9e36409abba2adbe413d6fae
Js版本
/*
* function TreeNode(x) {
* this.val = x;
* this.left = null;
* this.right = null;
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
function isCompleteTree(root) {
// write code here
if (root === null) return true;
let arr = [];
let flag = false;
arr.push(root);
while (arr.length !== 0) {//每一次while循环遍历一层
let len = arr.length;
for (let i = 0; i < len; ++i) {
let cur = arr.shift();
if (cur === null) flag = true;
else {
if (flag) return false;
arr.push(cur.left);
arr.push(cur.right);
}
}
}
return true;
}
module.exports = {
isCompleteTree: isCompleteTree,
};
此题中的for循环可以省略，若省略则每一次while循环遍历一个节点，而不是一层节点，但仍是层序遍历
判断完全二叉树思路：按层序遍历，若遍历到了空节点后续存在非空节点，则一定不是完全二叉树，若遍历到空节点后续全为空节点，则为完全二叉树
