Simple Python O(n) recursive solution with explanation (beats 90%)


  • 0
    P

    The idea is to recursively compute the depth at each node, but along with that (in the same recursive call) also determine if the subtree starting at that node is balanced. A subtree is balanced if abs(root.left_depth - root.right_depth) <= 1 and both left subtree and right subtree are balanced. Here is the solution:

    class Solution(object):
        def isBalanced(self, root):
    
            def depth(r):
                if r is None:
                    return (0, True)
    
                ld, is_left_bal = depth(r.left) if r.left else (0, True)
                rd, is_right_bal = depth(r.right) if r.right else (0, True)
                d = max(ld, rd) + 1
                
                if is_left_bal and is_right_bal and abs(rd-ld) <= 1:
                    is_bal = True
                else:
                    is_bal = False
                
                return d, is_bal
            
            return depth(root)[1]
    
    # 226 / 226 test cases passed.
    # Status: Accepted
    # Runtime: 72 ms
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.