2.0 Balanced Binary Tree

Description

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.

Method

1. the method to check wether a tree is a balanced binary tree is to look at the height of the tree. recursive
2. follow up: decrease the times of calculating the depth of tree we can use some special value to stand of illegal states

Time and Space Complexity

o(n^2)

o(n)

Code

method one: public class Solution {

     public boolean isBalanced(TreeNode root) {
       if (root == null){
           return true;
       }
       if (Math.abs(getDepth(root.left) - getDepth(root.right)) > 1){
           return false;
       }
       return isBalanced(root.left) && isBalanced(root.right);
       }

       public int getDepth(TreeNode root){
    if (root == null){
        return 0;
    }
    if (root.left == null && root.right == null){
        return 1;
    }
    return 1 + Math.max(getDepth(root.left), getDepth(root.right));
       }

}

method two:

      public boolean isBalanced(TreeNode root) {
      if (checkDepth(root) == -1){
          return false;
      }
      return true;


     }

     public int checkDepth(TreeNode root) {
      if (root == null){
          return 0;
      }
      int leftDepth = checkDepth(root.left);
      if (leftDepth == -1){
          return -1;
      }
      int rightDepth = checkDepth(root.right);
      if (rightDepth == -1){
          return -1;
      }

      if (Math.abs(leftDepth - rightDepth) > 1){
          return -1;
      }
      return 1 + Math.max(leftDepth, rightDepth);
}