# Balanced Binary Tree

## Question

### Problem Statement

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.

## 题解1 - 递归

### C++ Recursion with extra bool variable

/**
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: True if this Binary tree is Balanced, or false.
*/
bool isBalanced(TreeNode *root) {
if (NULL == root) {
return true;
}

bool result = true;
maxDepth(root, result);

return result;
}

private:
int maxDepth(TreeNode *root, bool &isBalanced) {
if (NULL == root) {
return 0;
}

int leftDepth = maxDepth(root->left, isBalanced);
int rightDepth = maxDepth(root->right, isBalanced);
if (abs(leftDepth - rightDepth) > 1) {
isBalanced = false;
// speed up the recursion process
return INT_MAX;
}

return max(leftDepth, rightDepth) + 1;
}
};


### C++

/**
* forked from http://www.jiuzhang.com/solutions/balanced-binary-tree/
* Definition of TreeNode:
* class TreeNode {
* public:
*     int val;
*     TreeNode *left, *right;
*     TreeNode(int val) {
*         this->val = val;
*         this->left = this->right = NULL;
*     }
* }
*/
class Solution {
public:
/**
* @param root: The root of binary tree.
* @return: True if this Binary tree is Balanced, or false.
*/
bool isBalanced(TreeNode *root) {
return (-1 != maxDepth(root));
}

private:
int maxDepth(TreeNode *root) {
if (NULL == root) {
return 0;
}

int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
if (leftDepth == -1 || rightDepth == -1 || \
abs(leftDepth - rightDepth) > 1) {
return -1;
}

return max(leftDepth, rightDepth) + 1;
}
};


### Java

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isBalanced(TreeNode root) {
return maxDepth(root) != -1;
}

private int maxDepth(TreeNode root) {
if (root == null) return 0;

int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
if (leftDepth == -1 || rightDepth == -1 ||
Math.abs(leftDepth - rightDepth) > 1) {

return -1;
}

return 1 + Math.max(leftDepth, rightDepth);
}
}