O(N) time python solution

  • 0

    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.