题解 | #判断是不是完全二叉树#

题目分析

1. 题目给出一课树的根节点作为输入
2. 题目要求我们判断该树是否为完全二叉树

方法一：层序遍历

• 实现思路
  • 对于完全二叉树，我们关心该树每一层从左到右是否是完全连续的
  • 因此层序遍历可以按照层的规则进行遍历
  • 在某一层的遍历过程中，如果我们遇到了一个空指针位置，则继续遍历有两种情况
    • 如果继续遍历，后面的节点全都是空指针节点，则说明该树是完全二叉树
    • 如果继续遍历，后面的节点重新出现了非空节点，则说明该树非完全二叉树

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return bool布尔型
#
class Solution:
    def isCompleteTree(self , root: TreeNode) -> bool:
        # write code here
        import queue
        q = queue.Queue()
        reachNull = False
        q.put(root)
        while not q.empty():
            cur = q.get()
            if not cur:
                reachNull = True    # 发现空节点
                continue
            else:
                if reachNull:       # 发现空节点之后存在非空节点
                     return False
                q.put(cur.left)     # 继续遍历左右节点
                q.put(cur.right)
        return True

复杂度分析

• 时间复杂度：$O(n)O(n)$，对所有的节点都需要遍历一遍
• 空间复杂度：$O(n)O(n)$，引入了队列的结构，队列的空间最大开销取决于树中节点最多的一层，对于完全二叉树，最多的一层节点数量有$(n+1)\mathrm{/}2(n+1)/2$个节点，可以达到$O(n)O(n)$的数量级

方法二：广度优先遍历编号

• 实现思路
  • 在完全二叉树中，如果根节点编号为1，按照层序的顺序继续编号下去的话，则对于完全二叉树中任何一个节点node的编号i，我们都有如下特征
  $\mathrm{编}\mathrm{号}(node\mathrm{.}left)=2\times i\mathrm{编}\mathrm{号}(node\mathrm{.}right)=2\times i+1编号(node.left)\; =\; 2\times i\backslash \backslash \; 编号(node.right)\; =\; 2\times i+1$
  • 因此我们同时进行两个计数操作
    • 1. 计数当前遍历访问的节点是第几个节点
    • 2. 计数在完全二叉树中，当前访问的节点在完全二叉树中的编号
  • 如果最终得到的两个值相同，说明该树是一棵完全二叉树
  • 如果最终得到的两个值不同，说明该树不是一棵完全二叉树

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return bool布尔型
#
class Solution:
    def isCompleteTree(self , root: TreeNode) -> bool:
        # write code here
        nodes = [(root, 1)]
        i = 0
        while i < len(nodes):
            node, v = nodes[i]
            i += 1                                    # 计数当前是第几个节点
            if node:
                nodes.append((node.left, 2*v))        # 继续为左子节点编号
                nodes.append((node.right, 2*v+1))     # 继续为右子节点编号
        return nodes[-1][1] == i

复杂度分析

• 时间复杂度：$O(n)O(n)$，对所有的节点遍历一次的时间代价
• 空间复杂度：$O(n)O(n)$，用一个列表记录了所有的节点信息和编号的空间代价