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

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

final class TreeInfo {
    public final int height;
    public final boolean balanced;
    
    public TreeInfo(int height, boolean balanced) {
        this.height = height;
        this.balanced = balanced;
    }
}

class Solution {
    public boolean isBalanced(TreeNode root) {
        TreeInfo res = helper(root);
        return res.balanced;
    }
    
    private TreeInfo helper(TreeNode root) {
        if(root == null) return new TreeInfo(0, true);
        
        TreeInfo resLeft = helper(root.left);
        TreeInfo resRight = helper(root.right);
        
        if(!resLeft.balanced || !resRight.balanced)
            return new TreeInfo(0, false);
        else {
            if(Math.abs(resLeft.height - resRight.height) > 1)
                return new TreeInfo(0, false);
            else
                return new TreeInfo(Math.max(resLeft.height, resRight.height) + 1, true);
        }
    }
}

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