LeetCode-958.二叉树的完全性校验

发表于 分类于

题目描述

给定一个二叉树的root，确定它是否是一个完全二叉树。

在一个 完全二叉树 中，除了最后一个关卡外，所有关卡都是完全被填满的，并且最后一个关卡中的所有节点都是尽可能靠左的。它可以包含 1 到 2h节点之间的最后一级h。

示例1

1
2
3
输入：root = [1,2,3,4,5,6]
输出：true
解释：最后一层前的每一层都是满的（即，结点值为 {1} 和 {2,3} 的两层），且最后一层中的所有结点（{4,5,6}）都尽可能地向左。

示例2

1
2
3
输入：root = [1,2,3,4,5,null,7]
输出：false
解释：值为 7 的结点没有尽可能靠向左侧。

题解

借助层序遍历的思路，添加标记flag，表示遍历到某层时是否遇到空节点。

开始层序遍历时，flag默认为false，在遍历到某层时遇到空节点，flag置为true；如果后面遍历中该层还有其他节点，则不是完全二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func isCompleteTree(_ root: TreeNode?) -> Bool {
  var queue = [root]
  var flag = false
  while !queue.isEmpty {
    var count = queue.count
    while count > 0 {
      let cur = queue.removeFirst()
      if cur === nil {
        flag = true
      } else {
        if flag {
          return false
        }
        queue.append(cur?.left)
        queue.append(cur?.right)
      }
      count -= 1
    }
  }
  return true
}