110.md

Solution 1 Top-down

naive implementaion

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        if not root: return True
        return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \
            self.isBalanced(root.left) and self.isBalanced(root.right)

    def depth(self, root):
        if not root: return 0
        return max(self.depth(root.left), self.depth(root.right)) + 1

Add memoization to avoid repeating computation.

class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        map = {None: 0}
        # use getHeight to store all node's height in map
        def getHeight(root, map):
            if root in map:
                return map[root]
            
            height = 1 + max(getHeight(root.left, map), getHeight(root.right, map))
            
            map[root] = height
            return height
        
        getHeight(root, map)
        return self.helper(root, map)
    
    def helper(self, root, map):
        if not root:
            return True
        if abs(map[root.left] - map[root.right]) > 1:
            return False
        return self.helper(root.left, map) and self.helper(root.right, map)

Solution 2 Bottom-up + pruning

refer to here.

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        # return tree depth if is balanced; else return -1
        def getTreeDepth(root):
            if not root: return 0

            left = getTreeDepth(root.left)
            # left subtree is not balanced, eary pruning
            if left == -1: return -1

            right = getTreeDepth(root.right)
            if right == -1: return -1

            return max(left, right)+1 if abs(left-right)<=1 else -1
        
        return getTreeDepth(root) != -1