这里的深度指的是二叉树从根结点到叶结点最大的高度,比如只有一个结点,则深度为1,如果有N层,则高度为N。
int depth(BTNode* root) { if (root == NULL) return 0; else { int lDepth = depth(root->left); //获取左子树深度 int rDepth = depth(root->right); //获取右子树深度 return lDepth>rDepth? lDepth+1: rDepth+1; //取较大值+1即为二叉树深度 } } 复制代码那么如何从功能上理解 depth 函数呢?我们可以知道定义该函数的目的就是求二叉树深度,也就是说我们要是完成了函数 depth,那么 depth(root) 就能正确返回以 root 为根结点的二叉树的深度。因此我们的代码中 depth(root->left) 返回左子树的深度,而depth(root->right) 返回右子树的深度。尽管这个时候我们还没有写完 depth 函数,但是我们相信 depth 函数能够正确完成功能。因此我们得到了 lDepth 和rDepth,而后通过比较返回较大值加1为二叉树的深度。
如果不好理解,可以想象在 depth 中调用的函数 depth(root->left) 为另外一个同样名字完成相同功能的函数,这样就好理解了。注意 Base Case,这里就是当 root==NULL 时,则深度为0,函数返回0。
2.3)判断二叉树是否平衡一颗平衡的二叉树是指其任意结点的左右子树深度之差不大于1。判断一棵二叉树是否是平衡的,可以使用递归算法来实现。
int isBalanceBTTop2Down(BTNode *root) { if (!root) return 1; int leftHeight = btHeight(root->left); int rightHeight = btHeight(root->right); int hDiff = abs(leftHeight - rightHeight); <span>if</span> (hDiff > 1) <span>return</span> 0; <span>return</span> isBalanceBTTop2Down(root->left) && isBalanceBTTop2Down(root->right);}
复制代码
该函数的功能定义是二叉树 root 是平衡二叉树,即它所有结点的左右子树深度之差不大于1。首先判断根结点是否满足条件,如果不满足,则直接返回 0。如果满足,则需要判断左子树和右子树是否都是平衡二叉树,若都是则返回1,否则0。
2.4)排列算法排列算法也是递归的典范,记得当初第一次看时一层层跟代码,头都大了,现在从函数功能上来看确实好理解多了。先看代码:
/** * 输出全排列,k为起始位置,n为数组大小 */ void permute(int a[], int k, int n) { if (k == n-1) { printIntArray(a, n); // 输出数组 } else { int i; for (i = k; i < n; i++) { swapInt(a, i, k); // 交换 permute(a, k+1, n); // 下一次排列 swapInt(a, i, k); // 恢复原来的序列 } } } 复制代码首先明确的是 perm(a, k, n) 函数的功能:输出数组 a 从位置 k 开始的所有排列,数组长度为 n。这样我们在调用程序的时候,调用格式为 perm(a, 0, n),即输出数组从位置 0 开始的所有排列,也就是该数组的所有排列。基础条件是 k==n-1,此时已经到达最后一个元素,一次排列已经完成,直接输出。否则,从位置k开始的每个元素都与位置k的值交换(包括自己与自己交换),然后进行下一次排列,排列完成后记得恢复原来的序列。
假定数组a aan na a =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到n个数字 */ void combination(int a[], int n) { int *select = (int *)calloc(sizeof(int), n); // select为辅助数组,用于存储选取的数 int k; for (k = 1; k <= n; k++) { combinationUtil(a, n, 0, k, select); } }/*