Problem
Given the root of a binary tree, return true if the tree is height-balanced. Otherwise, return false.A binary tree is height-balanced if, for every node, the height difference between its left and right subtrees is no more than 1.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
root = [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
Output
true Solution
This solution uses Depth-First Search (DFS) with recursion. Instead of calculating the height of each subtree separately, the height and balance status are determined in a single traversal.The recursive method returns the height of a subtree. If any subtree is unbalanced, it returns
-1 to indicate that the tree is not balanced.
For each node, the heights of its left and right subtrees are compared. If their difference is greater than 1, the subtree is unbalanced. Otherwise, the current node's height is returned.
public boolean isBalanced(TreeNode root) {
return height(root) != -1;
}
private int height(TreeNode node) {
if (node == null) {
return 0;
}
int leftHeight = height(node.left);
if (leftHeight == -1) {
return -1;
}
int rightHeight = height(node.right);
if (rightHeight == -1) {
return -1;
}
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
return 1 + Math.max(leftHeight, rightHeight);
}
Complexity
Each node in the binary tree is visited only once, resulting in a time complexity ofO(n). The recursive call stack can grow up to the height of the tree, resulting in an extra space complexity of
O(h), where h is the height of the tree.