Leetcode 110: Balanced Binary Tree

https://leetcode.com/problems/balanced-binary-tree/

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Please check the clear definition of this problem: https://leetcode.com/discuss/59/different-definitions-balanced-result-different-judgments

 

Code 1

# 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
        """
        return self.helper(root) != -1
    
    def helper(self, root):
        if not root:
            return 0
        
        left_depth = self.helper(root.left)
        right_depth = self.helper(root.right)
        if left_depth >= 0 and right_depth >= 0 and abs(left_depth-right_depth) <=1:
            return max(left_depth, right_depth)+1
        else:
            return -1

Idea

Use dfs to get depth of every node. Whenever one node has inbalancing left and right subtrees, it returns -1 as an indicator. Note how different code 1 is with code 2. In code 1, every node is traversed exactly once therefore code takes O(N) time. In code 2, O(NlogN) time is needed because the nodes on the same level of the binary tree need calling O(N)  times `self.getHeight(root)` in total.

 

Code 2:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param {TreeNode} root
    # @return {boolean}
    def isBalanced(self, root):
        if not root:
            return True

        return abs(self.getHeight(root.left) - self.getHeight(root.right)) < 2 and self.isBalanced(root.left) and self.isBalanced(root.right)

    def getHeight(self, root):
        if not root:
            return 0

        return 1 + max(self.getHeight(root.left), self.getHeight(root.right))

 

Reference

https://leetcode.com/discuss/22898/the-bottom-up-o-n-solution-would-be-better