题目描述

[EN | CN]

给定一个二叉树,确定它是否是一个完全二叉树

完全二叉树的定义如下:

若设二叉树的深度为 h,除第 h 层外,其它各层(1h-1)的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。(注:第 h 层可能包含 12h 个结点。)

示例 1:

1
2
3
4
5
6
7
8
9
1
    /      \
   2        3
 /   \    /
4     5 6

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

示例 2:

1
2
3
4
5
6
7
8
9
1
    /      \
   2        3
 /   \        \
4     5        7

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

提示:

树中将会有 1 到 100 个结点。

解法 1:直接解法

思路还算是比较简单的,用两个数组分别维持当前层(curr_level)、下一层(next_level)的结点,然后遍历当前层的结点:

  • 如果当前结点不为空,则将它左右子结点加入到下一层数组中;
  • 如果为空,则说明已经到头了,此时再判断当前层未遍历的结点、下一层结点全部为空即可。

假设结点数量为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(n)$,跟结点数量一致。

实现与结果如下:

 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.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isCompleteTree(self, root: TreeNode) -> bool:
        curr_level, next_level = [root], []

        is_none_list = lambda l: len(l) == 0 or len(set(l)) == 1 and l[0] == None

        while True:
            for i, node in enumerate(curr_level):
                if node is not None:
                    next_level.extend([node.left, node.right])

                else:
                    # Rest nodes in current level
                    if i != len(curr_level) - 1:
                        rest_nodes = curr_level[i + 1:]
                        if not is_none_list(rest_nodes):
                            return False

                    # Nodes in next level
                    if not is_none_list(next_level):
                        return False
                    return True

            curr_level, next_level = next_level, []
  • 执行用时:40 ms,在所有 Python3 提交中击败了 72.05% 的用户。
  • 内存消耗:13.6 MB,在所有 Python3 提交中击败了 7.14% 的用户。