笔试算法题（16）：二叉树深度计算 & 字符串全排列

出题：要求判断二元树的深度（最长根节点到叶节点的路径）；

分析：二元递归不容易使用循环实现

解题：

 1 struct Node {
 2         int value;
 3         Node *left;
 4         Node *right;
 5 };
 6 /**
 7  * 首先考虑递归结束条件
 8  * 然后考虑问题分解
 9  * 最后考虑问题合并
10  * */
11 int TreeDepth(Node *root) {
12         if(root == NULL) return 0;
13         int leftDepth=0;
14         int rightDepth=0;
15         if(root->left != NULL)
16                 leftDepth=TreeDepth(root->left);
17         if(root->right != NULL)
18                 rightDepth=TreeDepth(root->right);
19 
20         if(leftDepth > rightDepth)
21                 return leftDepth+1;
22         else
23                 return rightDepth+1;
24 }

出题：输入一个字符串，要求输出字符串中字符的所有排列与组合；

分析：

排列（所有元素组成的所有有序序列）：建立正确的求排列组合的思维，一位一位的考虑则使用递归处理子序列，每一位有不同的交换方式则使用循环交换不同位置的元素，注意递归之后的还原。由于当前索引元素只与其之后的元素交换，所以不会引入重复；
组合（不同元素组成的无序集合）：组合问题可以转换成为每一个元素是否出现问题，则使用0/1状态表示元素的出现与否，然后整体框架与排列类似；

解题：

 1 /**
 2  * 首先考虑递归结束条件：当index到达最后一个元素的时候
 3  * 说明可以输出一次序列
 4  * 然后考虑递归条件：将当前index指向的元素依次与array
 5  * 中index之后的元素交换，然后进行递归，递归之后需要
 6  * 将交换还原
 7  * */
 8 void arrange(char *array, int length, int index) {
 9         if(length == index+1) {
10                 printf("
");
11                 for(int i=0;i<length;i++)
12                         printf("%c, ", array[i]);
13                 printf("
");
14         }
15 
16         int temp;
17         for(int i=index;i<length;i++) {
18                 temp=array[index];
19                 array[index]=array[i];
20                 array[i]=temp;
21 
22                 arrange(array,length, index+1);
23 
24                 temp=array[index];
25                 array[index]=array[i];
26                 array[i]=temp;
27         }
28 }
29 void combination(char *array, bool *isShown, int length, int index) {
30         if(length==index) {
31                 printf("
*");
32                 for(int i=0;i<length;i++) {
33                         if(isShown[i])
34                                 printf("%c",array[i]);
35                 }
36                 return;
37         }
38 
39         for(int i=0;i<2;i++) {
40                 isShown[index]=i;
41                 combination(array, isShown, length, index+1);
42         }
43 
44 }
45 int main() {
46         char array1[]="abcd";
47         char array2[]="abc";
48         bool isShown[3];
49         combination(array2, isShown, 3, 0);
50         //arrange(array1,4,0);
51         return 0;
52 }