Friday, December 12, 2014

Balanced Binary Tree

This problem is a little bit tricky to me. The basic idea for all Tree problems is always traversal + recursion. In this problem, we need to check if the depth of each left and right subtree has a difference larger than 1. If it has,  return -1. If not, keep traverse the tree.




public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
 
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null)
            return true;
        return maxDepth(root) != -1;
    }
    private int maxDepth(TreeNode root)
    {
        if (root == null)
            return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        //if left subtree or right subtree has maxDepth greater than one or the maxDepth between left and right is greater than one, then the tree is not balanced 
        if (left == -1 || right == -1 || Math.abs(left - right) > 1)
            return -1;
        return Math.max(left, right) + 1;
    }
}

No comments:

Post a Comment