# balanced binary tree

## balanced binary tree

### DFS

If a node is balanced, it must satisfy the follow condition.

- Both its left and right children must be balanced.
- The hight difference between two children must be at most one.

```
1 /**
2 * Definition for binary tree
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8 * };
9 */
10 class Solution {
11 public:
12 bool isBalanced(TreeNode *root) {
13 if ( !root ) {
14 return true;
15 }
16 if ( !isBalanced(root->left) || !isBalanced(root->right) ) {
17 return false;
18 }
19 int l = height(root->left);
20 int r = height(root->right);
21 if ( l-r > 1 || l-r< -1 ) {
22 return false;
23 }
24 return true;
25 }
26 int height( TreeNode* root ) {
27 if ( !root ) {
28 return 0;
29 }
30 int l = height(root->left);
31 int r = height(root->right);
32 return max(l,r)+1;
33 }
34 };
```