Check Completeness of a Binary Tree (LC958)

  31 May 2019

By Wen Xu

binary tree recursion

Solution

# 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:
        
        def height(root)->int:
            if not root:
                return 0
            return 1 + max(height(root.left), height(root.right))
        
        def isFull(root)->bool:
            if not root:
                return True
            if not isFull(root.left) or not isFull(root.right):
                return False
            if height(root.left) != height(root.right):
                return False
            return True
        
        
        if not root:
            return True
        if not self.isCompleteTree(root.left) or not self.isCompleteTree(root.right): #subtree is not complete
            return False
        if height(root.left) < height(root.right): #left height is smaller than right height
            return False
        if height(root.left) > height(root.right) + 1: #left height is larger than right height plus 1
            return False
        if height(root.left) == height(root.right): #left height equals right height, then left subtree must be full
            return isFull(root.left)
        if height(root.left) == height(root.right) + 1: #left height equals right height plus 1, then right subtree must be full
            return isFull(root.right)
        return True
        
        
comments powered by Disqus