1102 Invert a Binary Tree (25 分) 翻转二叉树并输出层次遍历和中序遍历

深藏阁楼爱情的钟 2024-04-17 23:20 145阅读 0赞

1102 Invert a Binary Tree (25 分)

The following is from Max Howell @twitter:

  1. 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. 8
  2. 1 -
  3. - -
  4. 0 -
  5. 2 7
  6. - -
  7. - -
  8. 5 -
  9. 4 6

Sample Output:

  1. 3 7 2 6 4 0 5 1
  2. 6 5 7 4 3 2 0 1
  3. #include<stdio.h>
  4. #include<string.h>
  5. #include<math.h>
  6. #include<iostream>
  7. #include<string>
  8. #include<sstream>
  9. #include<algorithm>
  10. #include<map>
  11. #include<set>
  12. #include<queue>
  13. #include<stack>
  14. #include<vector>
  15. using namespace std;
  16. #define inf 0x3f3f3f3f
  17. #define LL long long
  18. vector<int> vd;
  19. int l[20],r[20];
  20. void dfs(int u)
  21. {
  22. if(r[u]!=-1)dfs(r[u]);
  23. vd.push_back(u);
  24. if(l[u]!=-1)dfs(l[u]);
  25. }
  26. int main()
  27. {
  28. int n,i,j;
  29. char x,y;
  30. map<int,int> ma;
  31. scanf("%d",&n);
  32. for(i=0;i<n;i++)
  33. {
  34. getchar();
  35. scanf("%c %c",&x,&y);
  36. if(x=='-')
  37. l[i]=-1;
  38. else
  39. l[i]=x-'0',ma[x-'0']++;
  40. if(y=='-')
  41. r[i]=-1;
  42. else
  43. r[i]=y-'0',ma[y-'0']++;
  44. }
  45. int root;
  46. for(i=0;i<n;i++)
  47. {
  48. if(ma[i]==0)
  49. root=i;
  50. }
  51. queue<int> q;
  52. vector<int> v;
  53. q.push(root);
  54. while(!q.empty())
  55. {
  56. int u=q.front();
  57. v.push_back(u);
  58. q.pop();
  59. if(r[u]!=-1)
  60. q.push(r[u]);
  61. if(l[u]!=-1)
  62. q.push(l[u]);
  63. }
  64. dfs(root);
  65. for(i=0;i<v.size()-1;i++)
  66. printf("%d ",v[i]);
  67. printf("%d\n",v[v.size()-1]);
  68. for(i=0;i<vd.size()-1;i++)
  69. printf("%d ",vd[i]);
  70. printf("%d\n",vd[vd.size()-1]);
  71. }

发表评论

表情:
评论列表 (有 0 条评论,145人围观)

还没有评论,来说两句吧...

相关阅读