Sponsored
Sponsored
This approach involves recursively calculating the height of each subtree and checking if the subtrees are balanced by ensuring the difference in height is not more than one.
Time Complexity: O(N^2), where N is the number of nodes in the tree, as we recalculate the height of subtrees multiple times. Space Complexity: O(N) due to recursion stack.
1public class TreeNode {
2 public int val;
3 public TreeNode left;
4 public TreeNode right;
5 public TreeNode(int x) { val = x; }
6}
7
8public class Solution {
9 public bool IsBalanced(TreeNode root) {
10 if (root == null) return true;
11 int leftHeight = Height(root.left);
12 int rightHeight = Height(root.right);
13 return Math.Abs(leftHeight - rightHeight) <= 1 && IsBalanced(root.left) && IsBalanced(root.right);
14 }
15
16 private int Height(TreeNode node) {
17 if (node == null) return 0;
18 return Math.Max(Height(node.left), Height(node.right)) + 1;
19 }
20}The C# solution computes the height of a tree's nodes recursively through the Height method. Ensuring all nodes maintain balance, the IsBalanced method confirms node heights are within allowance and recurses.
This optimized approach calculates the height and balance status of a tree in a single recursive function, thus avoiding recalculations by returning both height and balanced status in form of tuples or objects.
Time Complexity: O(N). Space Complexity: O(N), which includes the recursion stack depth.
1#
We use a helper struct Result holding both height and balanced state. The checkBalance function recurses over nodes, aggregating this data, and halting early if imbalance is detected.