The following is from Max Howell @twitter:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
Now it’s your turn to prove that YOU CAN invert a binary tree!
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (<=10) which is the total number of nodes in the tree — and hence the nodes are numbered from 0 to N-1. Then N lines follow, each corresponds to a node from 0 to N-1, and gives the indices of the left and right children of the node. If the child does not exist, a “-” will be put at the position. Any pair of children are separated by a space.
Output Specification:
For each test case, print in the first line the level-order, and then in the second line the in-order traversal sequences of the inverted tree. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.
Sample Input:
|
1 2 3 4 5 6 7 8 9 |
8 1 - - - 0 - 2 7 - - - - 5 - 4 6 |
Sample Output:
|
1 2 |
3 7 2 6 4 0 5 1 6 5 7 4 3 2 0 1 |
去年的梗……
偷懒写了递归版的，反正最多只有 10 个节点。注意一下只有 1 个节点的情况就可以了。
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 |
#include<stdio.h> #include<stdlib.h> typedef struct tree_ { int number; struct tree_ *left; struct tree_ *right; } tree; int count[10]; typedef struct queue_ { int size; int capacity; int front; int rear; void **data; } queue; #define is_queue_empty(X) (!((X)->size)) queue *init_queue(int n) { queue *temp; temp=(queue *)malloc(sizeof(queue)); temp->size=0; temp->capacity=n; temp->front=0; temp->rear=-1; temp->data=(void **)malloc(n*sizeof(void *)); return temp; } int enqueue(queue *q,void *data) { if(q->size==q->capacity) { return 1; } q->size++; q->rear=(q->rear+1)%q->capacity; q->data[q->rear]=data; return 0; } int dequeue(queue *q,void **data) { if(q->size==0) { *data=NULL; return 1; } q->size--; *data=q->data[q->front]; q->front=(q->front+1)%q->capacity; return 0; } int delete_queue(queue *q) { free(q->data); free(q); return 0; } void level_order(tree *t) { queue *q; tree *temp; int flag=0; q=init_queue(10); enqueue(q,t); while(!is_queue_empty(q)) { dequeue(q,(void **)&temp); if(flag==0) { printf("%d",temp->number); flag=1; } else { printf(" %d",temp->number); } if(temp->left!=NULL) { enqueue(q,temp->left); } if(temp->right!=NULL) { enqueue(q,temp->right); } } printf("\n"); } void in_order_r(tree *root,int *flag) { if(root==NULL) { return ; } in_order_r(root->left,flag); if(*flag==0) { printf("%d",root->number); *flag=1; } else { printf(" %d",root->number); } in_order_r(root->right,flag); } void invert_r(tree *root) { tree *temp; if(root==NULL) { return ; } temp=root->left; root->left=root->right; root->right=temp; invert_r(root->left); invert_r(root->right); } int main() { tree t[10],*root; int n,i,flag=0; char buf[4]; scanf("%d",&n); getchar(); for(i=0;i<n;i++) { gets(buf); t[i].number=i; t[i].left=buf[0]=='-'?NULL:t+buf[0]-'0'; t[i].right=buf[2]=='-'?NULL:t+buf[2]-'0'; if(buf[0]!='-') { count[buf[0]-'0']=1; } if(buf[2]!='-') { count[buf[2]-'0']=1; } } for(i=0;i<n;i++) { if(t[i].left==NULL&&t[i].right==NULL) { continue; } if(count[i]!=1) { root=t+i; break; } } if(n==1) { root=t; } invert_r(root); level_order(root); in_order_r(root,&flag); } |