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.

solution 1. O(nlog(n))

/**

* Definition of TreeNode:

* public class TreeNode {

* public int val;

* public TreeNode left, right;

* public TreeNode(int val) {

* this.val = val;

* this.left = this.right = null;

* }

* }

*/

public class Solution {
/\*\*

 \* @param root: The root of binary tree.

 \* @return: True if this Binary tree is Balanced, or false.

 \*/

    public boolean isBalanced(TreeNode root) {

        // write your code here

        if (root == null) {

            return true;
        }



        int leftHeight = getHeight(root.left);

        int rightHeight = getHeight(root.right);

        if (Math.abs(leftHeight- rightHeight) > 1) {

            return false;

        } 

        return isBalanced(root.left) && isBalanced(root.right);



    }



    private int getHeight(TreeNode root) {

        if (root == null) {

            return 0;

        }



        int leftHeight = getHeight(root.left);

        int rightHeight = getHeight(root.right);

        return 1 + Math.max(leftHeight,rightHeight);

    }
}

solution2: O(n)

// key point 在求tree的height的同时判断是不是balanced,

/**

* public class TreeNode {

* public int key;

* public TreeNode left;

* public TreeNode right;

* public TreeNode(int key) {

* this.key = key;

* }

* }

*/

public class Solution {
  public boolean isBalanced(TreeNode root) {
    // Write your solution here.

    if (root == null) {

      return true;

    }

    return height(root) != -1;
  }

  private int height(TreeNode root) {
    if (root == null) {

      return 0;

    }



    int leftHeight = height(root.left);

    if (leftHeight == -1) {

      return -1;

    }



    int rightHeight = height(root.right);

    if (rightHeight == -1) {

      return -1;

    }



    if (Math.abs(rightHeight - leftHeight) > 1) {

      return -1;

    }


    return 1 + Math.max(rightHeight, leftHeight);
  }
 }