Dare2Solve
The problem is to determine whether a given binary tree is height-balanced. A binary tree is considered height-balanced if, for every node in the tree, the height difference between the left and right subtrees is at most 1.
A height-balanced tree ensures that the tree is as compact as possible, which makes operations like search, insert, and delete more efficient. The key observation is that a tree is balanced if and only if the left and right subtrees of every node are balanced and the difference in their heights is no more than 1.
Post-order Traversal:
Height Calculation:
Balance Check:
Return the Result:
The time complexity is (O(n)), where n
is the number of nodes in the tree. This is because each node is visited once during the traversal.
The space complexity is (O(h)), where h
is the height of the tree. This is due to the recursion stack, which at most will be as deep as the height of the tree.
class Solution {
public:
bool isBalanced(TreeNode* root) {
bool isBal = true;
std::function<int(TreeNode*)> maxDepth = [&](TreeNode* node) -> int {
if (!node) return 0;
int leftSub = maxDepth(node->left);
int rightSub = maxDepth(node->right);
if (std::abs(leftSub - rightSub) > 1) {
isBal = false;
}
return std::max(leftSub, rightSub) + 1;
};
maxDepth(root);
return isBal;
}
};
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
self.isBal = True
def maxDepth(node: Optional[TreeNode]) -> int:
if not node:
return 0
leftSub = maxDepth(node.left)
rightSub = maxDepth(node.right)
if abs(leftSub - rightSub) > 1:
self.isBal = False
return max(leftSub, rightSub) + 1
maxDepth(root)
return self.isBal
class Solution {
private boolean isBal = true;
public boolean isBalanced(TreeNode root) {
maxDepth(root);
return isBal;
}
private int maxDepth(TreeNode node) {
if (node == null) return 0;
int leftSub = maxDepth(node.left);
int rightSub = maxDepth(node.right);
if (Math.abs(leftSub - rightSub) > 1) {
isBal = false;
}
return Math.max(leftSub, rightSub) + 1;
}
}
var isBalanced = function (root) {
let isBal = true
var maxDepth = function (node) {
if (!node) return 0
let leftSub = maxDepth(node.left)
let rightSub = maxDepth(node.right)
if (Math.abs(leftSub - rightSub) > 1) {
isBal = false
}
return Math.max(leftSub, rightSub) + 1
}
maxDepth(root)
return isBal
};