LaneYang
1/12/2020 - 1:19 AM

## Check If Binary Tree Is Balanced.java

``````//Normal solution: get height then compare
//Time O(n log n): every layer O(n),  log n layer.
//Space O(h)
public class Solution {
public boolean isBalanced(TreeNode root) {
// base case
if (root == null) {
return true;
}
// check if left and right subtree is balanced, and if the node itself is
// balanced.
return isBalanced(root.left) && isBalanced(root.right)
&& Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1;
}
}

// Optimal solution:
//Time O(n) : ?? //TODO
//Space O(h): ??
/*
* because height must >= 0; return height of the tree if it is balanced, return
* -1 if it is unbalanced.
*/

public class Solution {
public boolean isBalanced(TreeNode root) {
return getHeightOrUnbalanced(root)>=0;
}

private int getHeightOrUnbalanced(TreeNode root) {
// Base case: reaches leaf , so return height which is 0
if (root == null) {
return 0;
}
// subproblem
int left = getHeightOrUnbalanced(root.left);
int right = getHeightOrUnbalanced(root.right);
// recursion rule
// check if left and right subtree is balanced
if (left == -1 || right == -1) {
return -1;
}
// if left and right subtree is balanced, check if this layer is balanced.
if (Math.abs(left - right) > 1) {
return -1;
}
// if balanced, return the height.
return Math.max(left,right)+1;

}
}
``````