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; } }
AdSense
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.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment