题目描述
校验一棵树是否为完全二叉树
完全二叉树定义：若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。（注：第 h 层可能包含 1~ 2h 个节点。）
来源：https://leetcode-cn.com/problems/check-completeness-of-a-binary-tree
如输入：
输出：true
输入：
输出：false
思路
1.逐层遍历节点，如果遇到一个为空的节点后，继续遍历再遇到非空节点，那么可以判断这棵树不是完全二叉树。
关于怎么逐层遍历可以看看之前做过的题：二叉树的层平均值
工具：队列
2.将每个节点依次标号，1、2、3、4....
有如下规律：第N个节点，其left=2N，right=2N+1
如果是完全二叉树，那么最后一个节点的标号=节点总数
如上面的第二个例子，最后一个节点的标号为7，但是总的节点数为6，所以这棵树不是完全二叉树，通过这个依据也可以判断是否完全二叉树
实现
//思路1的实现
fun isCompleteTree(root: TreeNode?): Boolean {
if (root == null) {
return false
}
val queue = LinkedList<TreeNode>()//利用队列将下一层的所有节点保存起来等待遍历
queue.offer(root)
var lastNode: TreeNode? = root//上一个遍历到的节点
while (!queue.isEmpty()) {
var size = queue.size
while (size > 0) {
--size
val node = queue.poll()
node?.let {
queue.offer(node.left)
queue.offer(node.right)
}
if (node != null && lastNode == null) {//如果上一个节点是null，并且当前遍历的节点不为null，那么可以判定这个树不是完全二叉树
return false
}
lastNode = node
}
}
return true
}
