给定一个二叉树,确定他是否是一个完全二叉树。
完全二叉树的定义:若二叉树的深度为 h,除第 h 层外,其它各层的结点数都达到最大个数,第 h 层所有的叶子结点都连续集中在最左边,这就是完全二叉树。(第 h 层可能包含 [1~2h] 个节点)
数据范围:节点数满足
样例图1:
样例图2:
样例图3:
{1,2,3,4,5,6}
true
{1,2,3,4,5,6,7}
true
{1,2,3,4,5,#,6}
false
class Solution: def isCompleteTree(self , root: TreeNode) -> bool: if root.left == root.right and root.left == None: return True tree = [None] * 100 stack = [(root,0)] while len(stack)>0: cur,i = stack.pop() if not cur.left is None: stack.append((cur.left,(i<<1)+1)) elif not cur.right is None: # 左空右值必错 return False if not cur.right is None: stack.append((cur.right,(i<<1)+2)) if i < 100 and cur.val != "#": tree[i] = 1 for i in range(1,99): if tree[i] is None and not tree[i+1] is None: return False return True想起了数组树
# 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 if root is None: return True queue = [root] is_missing_child = False while len(queue) > 0: node = queue.pop(0) # 针对缺失节点的情况进行判断 if node is None: is_missing_child = True continue elif is_missing_child: return False # 将左右子节点加入队列 queue.append(node.left) queue.append(node.right) return True
class Solution: def isCompleteTree(self , root: TreeNode) -> bool: # write code here Tree = [root] flag = 0 while Tree: temp = Tree.pop(0) if flag == 1 and temp != '#': return False if temp == '#': flag = 1 else: if temp.left: Tree.append(temp.left) else: Tree.append('#') if temp.right: Tree.append(temp.right) else: Tree.append('#') return True简单易懂,自己食用!
# 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: if not root: return True queue = [root] flag = False while queue: node = queue.pop() # 第一次碰到空节点,改一下标记 if not node: flag = True else: # 若该节点不空而且之前出现了空节点,则证明不是完全二叉树 if flag and len(queue) > 0: return False queue.insert(0, node.left) queue.insert(0, node.right) return True
class Solution: def isCompleteTree(self , root: TreeNode) -> bool: # write code here alist = [root] isLeaf = False while alist and not isLeaf: node = alist.pop() if not node: isLeaf = True else: alist.insert(0, node.left) alist.insert(0, node.right) complete = True for i in alist: if i: complete = False break return complete