Balanced Binary Tree

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.

思路：

一棵树是平衡二叉树，等价于两个子树都是平衡二叉树，并且两子树的深度差不超过1。

代码：

 1     int max(int a, int b){
 2         if(a > b)
 3             return a;
 4         return b;
 5     }
 6     int getDepth(TreeNode *root){
 7         if(root == NULL)
 8             return 0;
 9         if(root->left == NULL && root->right == NULL)
10             return 1;
11         return 1+max(getDepth(root->left), getDepth(root->right));
12     }
13     bool isBalanced(TreeNode *root) {
14         // Start typing your C/C++ solution below
15         // DO NOT write int main() function
16         if(root == NULL)
17             return true;
18         int d1 = getDepth(root->left), d2 = getDepth(root->right);
19         if(d1 - d2 > 1 || d1 - d2 < -1)
20             return false;
21         return isBalanced(root->left)&&isBalanced(root->right);
22     }