Description:
Given a binary tree, determine if it is height-balanced.
Examples:
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: trueSolution in Python:
Python
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
# Helper function to determine the height of the tree
# and check if it is balanced at the same time.
def check_balance(node):
# If node is None, it is balanced and height is 0.
if not node:
return 0, True
# Recursively check the left subtree.
left_height, left_balanced = check_balance(node.left)
# Recursively check the right subtree.
right_height, right_balanced = check_balance(node.right)
# Current node's height.
current_height = max(left_height, right_height) + 1
# Check if the current node is balanced.
current_balanced = left_balanced and right_balanced and abs(left_height - right_height) <= 1
return current_height, current_balanced
# Call the helper function starting from the root.
_, balanced = check_balance(root)
return balancedDetailed Comments:
- TreeNode Class Definition:
- The
TreeNodeclass defines the structure of each node in the binary tree. It has a valueval, and pointers to its left and right children.
- The
- isBalanced Method:
- This method is the entry point for determining if the tree is balanced. It uses a helper function to perform the actual checking.
- check_balance Function:
- This helper function recursively checks the balance of the tree.
- Base Case: If the current node is
None, the subtree is balanced, and its height is0. - Recursive Case: The function calculates the height and balance status of the left and right subtrees by recursively calling itself.
- Current Height: The height of the current node is
1plus the maximum height of its left and right subtrees. - Current Balanced Status: The current node is balanced if both its left and right subtrees are balanced, and the absolute difference in their heights is at most
1. - The function returns the height and balance status of the current subtree.
- Checking Balance:
- The
isBalancedmethod callscheck_balancestarting from the root. - The result of the balance check for the entire tree is returned as the final result.
- The
This approach ensures that we check the balance and compute the height of each subtree in a single pass, making it efficient with a time complexity of O(n), where n is the number of nodes in the tree.
Solution in Javascript:
JavaScript
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isBalanced = function(root) {
/**
* Helper function to determine the height of the tree
* and check if it is balanced at the same time.
* @param {TreeNode} node
* @return {Array} [height, balanced]
*/
function checkBalance(node) {
// If node is null, it is balanced and height is 0
if (node === null) {
return [0, true];
}
// Recursively check the left subtree
const [leftHeight, leftBalanced] = checkBalance(node.left);
// Recursively check the right subtree
const [rightHeight, rightBalanced] = checkBalance(node.right);
// Current node's height
const currentHeight = Math.max(leftHeight, rightHeight) + 1;
// Check if the current node is balanced
const currentBalanced = leftBalanced && rightBalanced && Math.abs(leftHeight - rightHeight) <= 1;
return [currentHeight, currentBalanced];
}
// Call the helper function starting from the root
const [, balanced] = checkBalance(root);
return balanced;
};Solution in Java:
Java
class Solution {
/**
* Determine if a binary tree is height-balanced.
* @param root The root node of the binary tree.
* @return True if the tree is balanced, false otherwise.
*/
public boolean isBalanced(TreeNode root) {
// Call the helper function to check the balance and get the height
return checkBalance(root)[1] == 1;
}
/**
* Helper function to check the balance of the tree.
* @param node The current node being checked.
* @return An array where the first element is the height of the tree
* and the second element is 1 if the tree is balanced, 0 otherwise.
*/
private int[] checkBalance(TreeNode node) {
// If the node is null, it's balanced and height is 0
if (node == null) {
return new int[]{0, 1};
}
// Recursively check the left subtree
int[] left = checkBalance(node.left);
// Recursively check the right subtree
int[] right = checkBalance(node.right);
// Calculate the current height
int height = Math.max(left[0], right[0]) + 1;
// Check if the current node is balanced
boolean balanced = left[1] == 1 && right[1] == 1 && Math.abs(left[0] - right[0]) <= 1;
// Return the height and balance status
return new int[]{height, balanced ? 1 : 0};
}
}Solution in C#:
C#
public class Solution {
/**
* Determine if a binary tree is height-balanced.
* @param root The root node of the binary tree.
* @return True if the tree is balanced, false otherwise.
*/
public bool IsBalanced(TreeNode root) {
// Call the helper function to check the balance and get the height
return CheckBalance(root).Item2;
}
/**
* Helper function to check the balance of the tree.
* @param node The current node being checked.
* @return A tuple where the first element is the height of the tree
* and the second element is true if the tree is balanced, false otherwise.
*/
private (int, bool) CheckBalance(TreeNode node) {
// If the node is null, it's balanced and height is 0
if (node == null) {
return (0, true);
}
// Recursively check the left subtree
var left = CheckBalance(node.left);
// Recursively check the right subtree
var right = CheckBalance(node.right);
// Calculate the current height
int height = Math.Max(left.Item1, right.Item1) + 1;
// Check if the current node is balanced
bool balanced = left.Item2 && right.Item2 && Math.Abs(left.Item1 - right.Item1) <= 1;
// Return the height and balance status
return (height, balanced);
}
}