Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as: a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Approach1: Recursion
Intuitive way to solve this problem is to recursively check the left subtree and right subtree once we find that the difference height of the left subtree and right subtree is more than 1, we simply use -1 to sign the height is not valid, thus to return false. Otherwise, we return true.
Time: O(N) Space: O(N), N is the number of total nodes in the tree.
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
if(helper(root) == -1){
return false;
}
return true;
}
private int helper(TreeNode node){
if(node == null) return 0;
int l = helper(node.left);
int r = helper(node.right);
if(Math.abs(l-r) > 1 || l== -1 || r == -1) {//if l or r equals -1, it means this tree is not valid, should return -1.
return -1;
}
return Math.max(1+helper(node.left), 1+helper(node.right));//return the height.
}
}
