首页 > 代码库 > 笔试算法题（37）：二叉树的层序遍历 & 最长递增的数字串

笔试算法题（37）：二叉树的层序遍历 & 最长递增的数字串

2024-07-06 01:14:30   222人阅读

出题：要求层序遍历二叉树，从上到下的层次，每一层访问顺序为从左到右，并将节点一次编号，输出如下；如果只要求打印指定的level的节点，应该如何实现。
　　a
　　b  c
　　d  e  f  g
　　h  i
 

分析：

  • 原始的层序遍历类似于BFS，打印当前访问的节点curNode的序列号，并将其直接子节点放入队列queue中，然后从queue中取出下一个节点，直 到队列为空；此方法仅能按照层序打印所有节点，并不能区分每一层节点的数量；如果需要区分当前层次的节点，和当前层次节点的子节点，可以使用两个队列 queue1和queue2作为两个缓冲，当访问queue1中的节点时，当前节点的所有子节点放入queue2中，直到queue1队列为空，然后访问 queue2队列的节点，将对应的子节点放入queue1中；最终结束条件为queue1和queue2都为空；
  • 如果需要打印指定level的所有节点，可以再增加一个计数，也就是一次完全访问队列（queue1或者queue2）计数1，第一层为0，直到用户指定的level才进行打印，否则节点的序列号不打印；

解题：

 1 struct Node {
 2         int value;
 3         Node *left;
 4         Node *right;
 5 };
 6 
 7 class MyQueue {
 8 private:
 9         Node *array[];
10         int capability;
11         int length;
12         int head;
13         int tail;
14 public:
15         MyQueue(int n=5): array((Node**)malloc(sizeof(Node*)*n)), head(0),tail(0),capability(n), length(0) {}
16         ~MyQueue() {delete [] array;}
17 
18         bool isFull() {
19                 if(length == capability) return true;
20                 return false;
21         }
22         bool isEmpty() {
23                 if(length == 0) return true;
24                 return false;
25         }
26         int freeSlot() {
27                 return capability-length;
28         }
29         void setBack() {
30                 length=0;
31         }
32 /**
33  * head当前的指向位置是下一次将push的元素的
34  * */
35         bool push(Node *n) {
36                 if(isFull()) return false;
37                 array[head]=n;
38 
39                 head=(head+1)%(capability);
40                 length++;
41                 return true;
42         }
43 /**
44  * tail当前指向的位置是下一次将pop的元素的
45  * */
46         Node* pop() {
47                 if(isEmpty()) return false;
48                 int temp=tail;
49                 tail=(tail+1)%(capability);
50                 length--;
51                 return array[tail];
52         }
53 
54         void showQueue() {
55                 int i=tail;
56                 int temp=length;
57                 printf("\ncurrent queue elements: \n");
58                 while(temp>0) {
59                         printf("%d, ",array[i++]->value);
60                         temp--;
61                 }
62         }
63 };
64 
65 void HierarchyPrint(Node *root) {
66         MyQueue *queue1=new MyQueue();
67         MyQueue *queue2=new MyQueue();
68 
69         int level=-1;
70         queue1->push(root);
71         Node *temp;
72 
73         while(true) {
74                 level++;
75                 printf("Level %d:\n",level);
76 
77                 while(!queue1->isEmpty()) {
78                         temp=queue1->pop();
79                         printf("%d\t",temp->value);
80                         if(temp->left!=NULL)
81                                 queue2->push(temp->left);
82                         if(temp->right!=NULL)
83                                 queue2->push(temp->right);
84                 }
85 
86                 level++;
87                 printf("Level %d:\n",level);
88 
89                 while(!queue2->isEmpty()) {
90                         temp=queue2->pop();
91                         printf("%d\t",temp->value);
92                         if(temp->left!=NULL)
93                                 queue1->push(temp->left);
94                         if(temp->right!=NULL)
95                                 queue1->push(temp->right);
96                 }
97         }
98 }

 

出题：给定一个字符串，要求找到其中最长递增的数字串，给定函数接口如下：
　　　　　　int ContinuMax(char *input, char **output)
　　　input为输入的字符串，要求返回连续最长数字串的长度，并将起始位置赋值给output；

分析：看似简单的一个功能实现其实需要注意不少问题；

解题：

 1 /**
 2  * 注意当数字序列递减又递增的情况，如何设置tempMax的值
 3  * 注意判定第一个是数字的字符位置
 4  * */
 5 int LIN(char *input, char **output) {
 6         int max=0,tempMax=0;
 7         char *index=input;
 8 
 9         while(*index!=‘\0‘) {
10                 if(*index<‘0‘||*index>‘9‘) {
11                         /**
12                          * 如果是非数字，则将tempMax清零
13                          * */
14                         tempMax=0;
15                 }else if(*(index-1)>‘0‘ && *(index-1)<‘9‘) {
16                         /**
17                          * 此处需要保证当前index是数字，并且index-1也
18                          * 需要是数字
19                          * */
20                         if(*index - *(index-1)>=0) {
21                                 tempMax++;
22                                 if(max<tempMax) {
23                                         max=tempMax;
24                                         *output=index-tempMax+1;
25                                 }
26                         } else {
27                                 /**
28                                  * 如果数字序列有递减的，将tempMax设为1
29                                  * */
30                                 tempMax=1;
31                         }
32                 } else {
33                         /**
34                          * 当index为数字，index-1为非数字的情况
35                          * */
36                         tempMax=1;
37                 }
38                 index++;
39         }
40         return max;
41 }
42 
43 int main() {
44         char array[]="abcd12dfgr298679rg13";
45         char *output=NULL;
46         int length=LIN(array, &output);
47         if(output==NULL) {
48                 printf("\nthere is no int in array.");
49                 return 1;
50         }
51         for(int i=0;i<length;i++) {
52                 printf("%c",output[i]);
53         }
54         return 0;
55 }

 

 


联系
我们