1102. Invert a Binary Tree (25)

前端之家收集整理的这篇文章主要介绍了1102. Invert a Binary Tree (25)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
题目链接http://www.patest.cn/contests/pat-a-practise/1102
题目:

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. 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

分析:
题目中的原意是:给你一个树的输入,让你把数左右互换(invert)然后对其进行层序遍历和中序遍历。
不过可以有一个小trick,对待输入我们不把它当做是先左孩子再右孩子,而是当做是先右孩子再左孩子。
另外,对于这种序号已知的,结构体不用Node* lchild,而是直接用int lchild,会方便很多很多

AC代码
  1. #include <iostream>
  2. #include<stdio.h>
  3. #include<algorithm>
  4. #include<string>
  5. #include<vector>
  6. #include<queue>
  7. using namespace std;
  8. struct Node{
  9. int lchild;
  10. int rchild;
  11. int parent;
  12. Node() :lchild(-1),rchild(-1),parent(-1){}
  13. //因为不是用Node*,所以不能用是否等于NULL来判断
  14. //所以这里初始化全部用-1,方便用来判断
  15. }buf[10];
  16. int findRoot(int x){//找到根节点
  17. if (buf[x].parent != -1){
  18. return findRoot(buf[x].parent);
  19. }
  20. return x;
  21. }
  22. vector<int>ans;//为了答案的格式化输出,所以用一个vector存储顺序
  23. void level_order(int root){//层序遍历,需要和queue配合使用
  24. queue<int>Q;
  25. Q.push(root);
  26. while (!Q.empty()){
  27. int cur = Q.front();
  28. ans.push_back(cur);
  29. Q.pop();
  30. if (buf[cur].lchild != -1)
  31. Q.push(buf[cur].lchild);
  32. if (buf[cur].rchild != -1)
  33. Q.push(buf[cur].rchild);
  34. }
  35. }
  36. void in_order(int root){//中序遍历,先左再存储再右
  37. if (buf[root].lchild != -1)
  38. in_order(buf[root].lchild);
  39. ans.push_back(root);
  40. if (buf[root].rchild != -1)
  41. in_order(buf[root].rchild);
  42. }
  43. void print(vector<int> Vx){//对于vector的格式化输出
  44. for (int i = 0; i < Vx.size(); ++i){
  45. if(i) cout << " " << Vx[i];
  46. else cout << Vx[i];
  47. }
  48. }
  49. int main(){
  50. //freopen("F://Temp/input.txt","r",stdin);
  51. int n;
  52. cin >> n;
  53. for (int i = 0; i < n; i++){
  54. string l,r;
  55. cin >> r >> l;//point,先右后左可以直接实现invert树的效果
  56. if (r != "-"){
  57. buf[i].rchild = atoi(r.c_str());//孩子和父的两边都要互相记录
  58. buf[atoi(r.c_str())].parent = i;
  59. }
  60. if (l != "-"){
  61. buf[i].lchild = atoi(l.c_str());
  62. buf[atoi(l.c_str())].parent = i;
  63. }
  64. }
  65. int root = findRoot(0);//找到根节点
  66. ans.clear();
  67. level_order(root);
  68. print(ans);
  69. ans.clear();//记得要清空一下
  70. cout << endl;
  71. in_order(root);
  72. print(ans);
  73. cout << endl;
  74. return 0;
  75. }


截图:

——Apie陈小旭

猜你在找的设计模式相关文章