Leetcode 110 Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Input: root = [3,9,20,null,null,15,7]
Output: true

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Input: root = []
Output: true

• This question can be solved by Depth First Search and it is similar with question 104. Maximum Depth of Binary Tree.

• From qusetion 104, we learned that to find the maximum depth we need to use dfs and max. For this question, to find if the tree is balanced-height, we need to find left subtree height and right subtree height then get the difference between the left and right subtree. If the difference is greater than 1, then it is not balanced-height otherwise it is balanced-height tree. Note that if there is None node or 1 node, they are both balanced binary tree.

    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def dfs(root):
            if not root: return [True,0]
            
            left,right = dfs(root.left),dfs(root.right)
            balanced = (left[0] and right[0] and abs(left[1] - right[1]) <=1)
            return[balanced,1+max(left[1],right[1])]
        
        return dfs(root)[0]