I have heard people say it is easy but it took me some time to get this… 🙁

public class BalancedTree { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public boolean isBalanced(TreeNode root) { if (root == null) { return true; } else { int[] lh = _isBalanced(root); return lh == null ? false : true; } } private int[] _isBalanced(TreeNode root) { int[] def = new int[2]; def[0] = 0; def[1] = 0; if (root.left != null) { int[] tmp = _isBalanced(root.left); if (tmp != null) { def[0] = Math.max(tmp[0], tmp[1]) + 1; } else { return null; } } if (root.right != null) { int[] tmp = _isBalanced(root.right); if (tmp != null) { def[1] = Math.max(tmp[0], tmp[1]) + 1; } else { return null; } } if (def == null || Math.abs(def[0] - def[1]) > 1) { return null; } else { return def; } } }

Advertisements