1 bool is_balanced_2(BinaryTreeNode* pRoot, int* pDepth)
 2 {
 3     if(pRoot == NULL)
 4     {
 5         *pDepth = 0;
 6         return true;
 7     }
 8 
 9     int left, right;
10     if(is_balanced_2(pRoot->m_pLeft, &left) //左子树平衡
11         && is_balanced_2(pRoot->m_pRight, &right)) //右子树平衡
12     {
13         int diff = left - right;
14         if(diff <= 1 && diff >= -1)
15         {
16             *pDepth = 1 + (left > right ? left : right);
17             return true;
18         }
19     }
20 
21     return false;
22 }

1 bool IsBalanced(BinaryTreeNode* pRoot)
2 {
3     int depth = 0;
4     return is_balanced_2(pRoot, &depth);
5 }

2.4）排列算法

排列算法也是递归的典范，记得当初第一次看时一层层跟代码，头都大了，现在从函数功能上来看确实好理解多了。先看代码：

 1 void perm(int a[], int k, int N) { //k为起始位置，N为数组大小
 2     if (k == N-1) { 
 3         output(a, N); //输出排列
 4     } else {
 5         for (int i=k; i<N; i++) {
 6             swap(a, i, k); //交换
 7             perm(a, k+1, N); //下一次排列
 8             swap(a, i, k); //恢复原来的序列
 9         }
10     }
11 }

首先明确的是perm(a, k, N)函数的功能:输出数组a从位置k开始的所有排列，数组长度为N。这样我们在调用程序的时候，调用格式为perm(a, 0, N)，即输出数组从位置0开始的所有排列，也就是该数组的所有排列。基础条件是k==N-1，此时已经到达最后一个元素，一次排列已经完成，直接输出。否则，从位置k开始的每个元素都与位置k的值交换(包括自己与自己交换)，然后进行下一次排列，排列完成后记得恢复原来的序列。

假定数组a大小N=3，则程序调用perm(a, 0, 3)可以如下理解： 第一次交换0，0，并执行perm(a, 1, 3)，执行完再次交换0，0，数组此时又恢复成初始值。 第二次交换1，0（注意数组此时是初始值），并执行perm(a, 1, 3), 执行完再次交换1，0，数组此时又恢复成初始值。 第三次交换2，0，并执行perm(a, 1, 3)，执行完成后交换2，0，数组恢复成初始值。

也就是说，从功能上看，首先确定第0个位置，然后调用perm(a, 1, 3)输出从1开始的排列，这样就可以输出所有排列。而第0个位置可能的值为a[0], a[1],a[2]，这通过交换来保证第0个位置可能出现的值，记得每次交换后要恢复初始值。

如数组a={1,2,3}，则程序运行输出结果为：1 2 3 ，1 3 2 ，2 1 3 ，2 3 1 ，3 2 1 ，3 1 2 。即先输出以1为排列第一个值的排列，而后是2和3为第一个值的排列。

2.5）组合算法

组合算法也可以用递归实现，只是它的原理跟0-1背包问题类似。即要么选要么不选，注意不能选重复的数。完整代码如下：

 1 #include<iostream>
 2 using namespace std;
 3 #define N 3  //数组大小为3
 4 int select[N] = {0}; //选择数组，用于存储数组哪些数字被选中。
 5 /*输出数组中选中的数*/
 6 void output(int a[], int n)
 7 {
 8     for (int i=0; i<n; i++) {
 9         if (select[i])
10             cout << a[i] << " ";
11     }
12     cout << endl;
13 }
14 /*数组a从位置i开始选取k个数*/
15 void combination(int a[], int i, int k)
16 {
17     if (i > N) return; //位置超出数组范围直接返回，否则非法访问会出段错误
18     if (k == 0) {  //选取完了，输出选取的数字
19         output(a, N);
20     } else {
21         select[i] = 1;  
22         combination(a, i+1, k-1); //第i个数字被选取，从后续i+1开始选取k-1个数
23         select[i] = 0;
24         combination(a, i+1, k); //第i个数字不选，则从后续i+1位置开始还要选取k个数
25     }
26 }
27 
28 /*组合主函数，包括选取1到n个数字*/
29 void combination_helper(int a[], int n) {
30     for (int k=1; k<=n; k++) {
31         combination(a, 0, k);
32     }
33 }
34 
35 int main()
36 {
37     int a[N] = {1, 2, 3};
38     combination_helper(a, N);
39     return 0;
40 }

1 void printReverse(const char *str) {
2   if (!*str)
3     return;
4   printReverse(str + 1);
5   putchar(*str);
6 }