Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

 

Example 1:

Input: root = [3,9,20,null,null,15,7]

Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4]

Output: false

Example 3:

Input: root = []

Output: true

 

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode() {}

 *     TreeNode(int val) { this.val = val; }

 *     TreeNode(int val, TreeNode left, TreeNode right) {

 *         this.val = val;

 *         this.left = left;

 *         this.right = right;

 *     }

 * }

 */

class Solution {

    public boolean isBalanced(TreeNode root) {

       

       if(root == null) return true;

        if(root.left == null && root.right == null) return true;

       

        int lht = height(root.left);

        int rht = height(root.right);

       

        if(Math.abs(lht-rht)>1){

            return false;

        }

       

        boolean checkLeft = isBalanced(root.left);

        boolean checkRight = isBalanced(root.right);

       

        if(checkLeft == false || checkRight == false) return false;

       

        return true;

    }

    public static int height(TreeNode root)

    {

        if(root ==null) return 0;

       

        int leftheight=height(root.left);

        int rightheight=height(root.right);

       

        return 1+Math.max(leftheight,rightheight);

    }

}