Balanced Binary Tree
Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is defined as a binary tree in which the difference between the heights of its two subtrees cannot exceed 1 for any node in the tree.
Constraints:
- The number of nodes in the tree is in the range [0, 10^4].
- The input tree is represented as a binary tree where each node has a unique value.
Examples:
Input: [3,9,20,null,null,15,7]
Output: true
Explanation: The tree is balanced because the difference between the heights of its two subtrees cannot exceed 1 for any node in the tree.
Input: [1,2,2,3,3,null,null,4,4]
Output: false
Explanation: The tree is not balanced because the difference between the heights of its two subtrees exceeds 1 for the root node.
Solutions
Recursive Approach
This solution uses a recursive approach to calculate the height of each subtree and check if the tree is balanced. The time complexity is O(n) because each node is visited once, and the space complexity is O(h) because of the recursive call stack.
public
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
return Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
private int getHeight(TreeNode node) {
if (node == null) return 0;
return Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}
}Follow-up:
How would you optimize the solution to reduce the time complexity?
