首页 > 代码库 > 笔试算法题(09):查找指定和值的两个数 & 构造BST镜像树

笔试算法题(09):查找指定和值的两个数 & 构造BST镜像树

出题:输入一个已经升序排序的数组和一个数字;要求在数组中查找两个数,这两个数的和正好等于输入的那个数字,输出任意一对数字就可以,要求时间复杂度是O(n);

分析:对于升序排序的数组{…i…j…k…m……},只有可能是i+m=j+k(j和k可能是同一个数),所以可以从两边往中间收缩而忽视其他交叉相加的情况;

解题:

 1 void FindSumFactor(int *array, int length, int sum) {
 2         int left=0, right=length-1;
 3         while(true) {
 4                 /**
 5                  * 如果当前和比sum小,则left往右移动;
 6                  * 如果当前和比sum大,则right往左移动
 7                  * 由于每次仅有一个指针移动,所以left和right必定会重合
 8                  * 所以不用担心数组溢出问题
 9                  * */
10                 if(array[left]+array[right]<sum) {
11                         left++;
12                 } else if(array[left]+array[right]>sum) {
13                         right--;
14                 }
15 
16                 /**
17                  * 每一次都单独判断是否相等,这样可以处理left和right
18                  * 重叠,但是他们的和等于sum的情况
19                  * */
20                 if(array[left]+array[right]==sum) {
21                         printf("\nthe sum factors are: %d, %d\n",
22                                         array[left],array[right]);
23                         exit(0);
24                 }
25 
26                 if(left>=right) {
27                         printf("\nfail to find the sum factor\n");
28                         exit(0);
29                 }
30         }
31 }

 

出题:输入一棵二元查找树,要求使用递归和循环两种方式实现镜像树的生成,也就是新树中的左子树节点大于右子树节点;

分析:单源递归可以不用辅助结构就可以实现循环;多源递归(DFS和BFS)需要使用辅助结构实现循环;

解题:

 1 /**
 2  * 将当前current的左右子树交换,然后对左右子树递归调用本方法
 3  * 最后返回当前节点到上层树。注意当子树为NULL时候对应子树的
 4  * 设置
 5  * */
 6 Node* RecursiveMirrorTree(Node *current) {
 7         Node *temp=current->left;
 8         if(current->right != NULL) {
 9                 current->left=RecursiveMirrorTree(current->right);
10         } else
11                 /**
12                  * 此处一定需要注意,如果不改变的话则发生错误
13                  * */
14                 current->left=NULL;
15 
16         if(temp != NULL) {
17                 current->right=RecursiveMirrorTree(temp);
18         } else
19                 current->right=NULL;
20 
21         return current;
22 }
23 /**
24  * 对于单源递归(仅一处发生递归),普通循环就可以解决;对于多源递归
25  * (多处发生递归,如左右子树),则必须使用辅助数据结构,或者stack
26  * 或者queue
27  * */
28 void NonRecursiveMirrorTree(Node *root) {
29         MyStack *stack=new MyStack();
30         stack->push(root);
31         Node *temp, *current;
32         while(!stack->isEmpty()) {
33                 current=stack->pop();
34                 temp=current->left;
35 
36                 if(current->right != NULL) {
37                         current->left=current->right;
38                         stack->push(current->right);
39                 } else
40                         current->left=NULL;
41 
42                 if(temp != NULL) {
43                         current->right=temp;
44                         stack->push(temp);
45                 } else
46                         current->right=NULL;
47         }
48         delete stack;
49 }