CC4.1.java

/*4.1 Implement a function to check if a binary tree is balanced. For the purposes of this question, 
* a balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one.
*/


// Solution 1
public class Solution {
    public boolean balancedBinaryTree(TreeNode root) {
        if(root==null) return true;
        if(Math.abs(getHeight(root.left)-getHeight(root.right))>1) return false;
        return balancedBinaryTree(root.left) && balancedBinaryTree(root.right);
    }
    public int getHeight(TreeNode root) {
        if(root==null) return 0;
        return Math.max(getHeight(root.left), getHeight(root.right))+1;
    }
}


// Solution 2
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if(checkHeight(root)==-1) {
            return false;
        } else {
            return true;
        }
    }
    public checkHeight(TreeNode root) {
        if(root==null) return 0;
        int leftHeight = checkHeight(root.left);
        if(leftHeight==-1) return -1
        int rightHeight = checkHeight(root.right);
        if(rightHeight==-1 || Math.abs(leftHeight-rightHeight)>1) return -1;
        return Math.max(leftHeight, rightHeight)+1;
    }
}