LC 0958 [M] Check Completeness of a Binary Tree - ALawliet/algorithms GitHub Wiki
BFS
depth 3, 4 nodes in a row = pos 0,1,2,3
depth 4, 8 nodes in a row = pos 0,1,2,3,4,5,6,7
left (depth, pos) -> (depth + 1, pos * 2)
right (depth, pos) -> (depth + 1, pos * 2 + 1)
completeness = left-justified -> last node position is equal to len of nodes
use while level < len(Q):
instead of while Q: node = Q.popleft()
so we can skip the last level and check it at the end
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isCompleteTree(self, root: TreeNode) -> bool:
Q = [ (root, 1) ] # pos
level = 0
while level < len(Q):
node, pos = Q[level]
level += 1
if node.left:
Q.append( (node.left, 2*pos) )
if node.right:
Q.append( (node.right, 2*pos + 1) )
return Q[-1][1] == len(Q)