958. Check Completeness of a Binary Tree - cocoder39/coco39_LC GitHub Wiki

958. Check Completeness of a Binary Tree

bfs: level by level traversal. if a node is none, then all subsequent nodes should be none.

unlike regular bfs, the key difference is that we should append none child node into queue. alignment of None node is the key to identify completeness

class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        queue = collections.deque([root])
        stop = False
        while queue:
            node = queue.popleft()
            if not node:
                stop = True
            else:
                if stop:
                    return False
                queue.append(node.left)
                queue.append(node.right)
        return True

dfs: 1. count node count in the tree 2. pass index to dfs, ensure index is always smaller than count

class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        node_count = self.count(root)
        print(node_count)

        return self.dfs(root, 1, node_count)
    
    def dfs(self, node, index, node_count):
        if not node:
            return True
        
        if index > node_count:
            return False
        
        return self.dfs(node.left, 2*index, node_count) and self.dfs(node.right, 2*index+1, node_count)
    
    def count(self, node):
        if not node:
            return 0
        return 1 + self.count(node.left) + self.count(node.right)