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

  • 0

    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
                    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.