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);
}