## Wednesday, January 16, 2013

### [LeetCode] Balanced Binary Tree Solution

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 everynode never differ by more than 1.
» Solve this problem

[Thoughts]
recursion. For each node, check the left branch and right branch.

[Code]
1:    bool isBalanced(TreeNode *root) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      if(root == NULL) return true;
5:      int val = GetBalance(root);
6:      if(val ==-1) return false;
7:      return true;
8:    }
9:    int GetBalance(TreeNode* node)
10:    {
11:      if(node == NULL)
12:        return 0;
13:      int left = GetBalance(node->left);
14:      if(left == -1) return -1;
15:      int right = GetBalance(node->right);
16:      if(right == -1) return -1;
17:      if(left-right>1 || right-left>1)
18:        return -1;
19:      return left>right? left+1:right+1;
20:    }