首页 > 代码库 > 笔试算法题(37):二叉树的层序遍历 & 最长递增的数字串
笔试算法题(37):二叉树的层序遍历 & 最长递增的数字串
出题:要求层序遍历二叉树,从上到下的层次,每一层访问顺序为从左到右,并将节点一次编号,输出如下;如果只要求打印指定的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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。