110. Balanced Binary Tree

# Easy, DFS

1. Both of left and right subtrees are balanced?

2. max depth difference between left and right <= 1?

Solution 1:

1. Write maxDepth function to get the max depth of left and right subtrees

2. In main function, recusive to see each layer's balance and compute left and right maxDepth difference

Python效率低

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        # edge case
        if root == None:
            return True

        # regular case
        if abs(self.maxHeight(root.left) - self.maxHeight(root.right)) > 1:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)

    def maxHeight(self, root):
        if root == None:
            return 0
        
        return max(self.maxHeight(root.left), self.maxHeight(root.right))+1

Solution 2:

Help function: if one of left and right subtree is not balanced, or max depth difference > 1, return -1; otherwise return maxDepth.

Main function: return true or false according to help function.

Python效率极高

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        return self.getHeight(root) != -1

    def getHeight(self, root):
        # edge case
        if root == None:
            return 0
        
        # regular case
        left = self.getHeight(root.left)
        right = self.getHeight(root.right)
        
        if left == -1 or right == -1:
            return -1
        if abs(left - right) > 1:
            return -1
        
        return max(left, right)+1

Java

时间复杂度= $O(n)$ 分析：1. 每个节点要做的运算是 $O(1)$ ；2. 每个节点只做一次运算，无重复，一共有 $n$ 个节点，所以是 $O(n)$ ；3. 则 $T=O(1)*O(n)=O(n)$ .