My Python code using a trick


  • 0
    H

    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.