O(N) time python solution


  • 0
    Z

    Store height of each node while traversing from bottom to top.
    I'm using a list to store height for list in python is mutable.

    class Solution(object):
        def isBalanced(self, root):
            """
            :type root: TreeNode
            :rtype: bool
            """
            return self.helper(root)
            
        def helper(self, root, height=[0,]):
            if not root: return True
            left_height = [0,]
            right_height = [0,]
            is_left_balanced = self.helper(root.left, left_height)
            is_right_balanced = self.helper(root.right, right_height)
            height[0] = 1 + max(left_height[0], right_height[0])
            if abs(left_height[0] - right_height[0])>1: return False
            return is_left_balanced and is_right_balanced
    

Log in to reply
 

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