package com.leetcode.tree;

/**

* Created by charles on 4/5/17.

* 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.

*/

public class BalancedBinaryTree_110 {

public boolean isBalanced(TreeNode root) {

if (root == null) {

return true;

}

int leftHeight = depth(root.left);

int rightHeight = depth(root.right);

return isBalanced(root.left) && isBalanced(root.right) && Math.abs(leftHeight - rightHeight) <= 1;

}

private int depth(TreeNode root) {

if (root == null) {

return 0;

}

return Math.max(depth(root.left), depth(root.right)) + 1;

}

/** taking advantage height always be positive,

* then return negative for height means current tree is not balanced

*/

public boolean isBalancedII(TreeNode root) {

return maxDepth(root) != -1;

}

private int maxDepth(TreeNode root) {

if (root == null) {

return 0;

}

int left = maxDepth(root.left);

int right = maxDepth(root.right);

// early termination

if (left == -1 || right == -1 || Math.abs(left - right) > 1) {

return -1;

}

return Math.max(left, right) + 1;

}

}