Balanced Binary Tree

• LintCode: No.93-Balanced Binary Tree
• Problem:

  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.
  

• Example:

  Given binary tree A={3,9,20,#,#,15,7}, B={3,#,20,15,7}  
    A)  3            B)    3 
       / \                  \
      9  20                 20
        /  \                / \
       15   7              15  7  
  The binary tree A is a height-balanced binary tree, but B is not.
  

• Analysis:

  check every nodes is fit for rule recursively.
  

• Java:

  • Recursive:

    /**  
     * 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;
            } else if (Math.abs(maxDepth(root.left) - maxDepth(root.right)) > 1) {
                return false;
            } else {
                return isBalanced(root.left) && isBalanced(root.right); 
            }
        }
        private int maxDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
        }
    }
    

• Time Complexity:
  • O(n^2), n is the number of nodes