leetcode-110-easy

Balanced Binary Tree

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

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: true
Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]
Output: false
Example 3:

Input: root = []
Output: true
Constraints:

The number of nodes in the tree is in the range [0, 5000].
-104 <= Node.val <= 104

思路一：计算每个节点的高度，然后对比

public boolean isBalanced(TreeNode root) {
    if (root == null) return true;

    if (root.left == null && root.right == null) return true;
    else if (root.left != null && root.right != null) {
        if (Math.abs(height(root.left, 1) - height(root.right, 1)) > 1) return false;
        return isBalanced(root.left) && isBalanced(root.right);
    }
    else if (root.left == null) {
        return height(root.right, 1) <= 2;
    } else {
        return height(root.left, 1) <= 2;
    }
}

public int height(TreeNode root, int height) {
    if (root == null) return height;

    return Math.max(height(root.left, height + 1), height(root.right, height + 1));
}

思路二：看了一下题解，发现思路一的解法可以优化

public boolean isBalanced(TreeNode root) {
    if (root == null) return true;

    return (Math.abs(height(root.left, 1) - height(root.right, 1)) <= 1) && isBalanced(root.left) && isBalanced(root.right);
}