每日算法题—二叉树完全性校验

题目描述

校验一棵树是否为完全二叉树

完全二叉树定义：若设二叉树的深度为 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
    }