My Python code using a trick

  • 0

    The idea is to count the depth of left subtree and right subtree and compare them. But we should also know whether the subtrees are balanced. In Python, the function can return multiple variables (as a tuple). We can use this feature.

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    class Solution(object):
        def isBalanced(self, root):
            :type root: TreeNode
            :rtype: bool
            def check(r):
                if r == None:   return True, 0
                balanced1, h1 = check(r.left)
                balanced2, h2 = check(r.right)
                balanced = balanced1 and balanced2 and abs(h1-h2)<=1
                h = max(h1, h2) + 1
                return balanced, h
            balanced, h = check(root)
            return balanced

Log in to reply

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