PAT A1102 Invert a Binary Tree [反转二叉树]

PAT A1102 Invert a Binary Tree [反转二叉树]
强烈推介IDEA2021.1.3破解激活,IntelliJ IDEA 注册码,2021.1.3IDEA 激活码  

大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说PAT A1102 Invert a Binary Tree [反转二叉树],希望能够帮助大家进步!!!

题目描述

链接
反转一棵二叉树,给出原二叉树的每个结点的左右孩子,输出它的层序和中序遍历

分析

  • 反转二叉树就是存储时交换左右结点,也可以遍历时交换遍历次序
  • 如何找root,别人用的have[i]=1标记,我用的二重循环
  • 处理输入输出,用string+stoi更简单,我用的char*和自己写的stoi,然后string和%s都是以空格回车tab作为输入结束
  • 输入整行的话,string用getline(cin,str), char用gets(s)
  • 别人好像有更好的写法:一个dfs输出层序和中序,我写的是分开的,先研究下别人的
    • 已知根结点,用递归的方法可以把中序遍历的结果push_back到数组v1里面,直接输出就是中序,排序输出就是层序(排序方式,层数小的排前面,相同层数时,index大的排前面)
    • 我搞不懂为啥不可以直接index排

别人的

#include <iostream> #include <vector> #include <algorithm> using namespace std; struct node { int id, l, r, index, level; } a[100]; vector<node> v1; void dfs(int root, int index, int level) { if (a[root].r != -1) dfs(a[root].r, index * 2 + 2, level + 1); v1.push_back({root, 0, 0, index, level}); if (a[root].l != -1) dfs(a[root].l, index * 2 + 1, level + 1); } bool cmp(node a, node b) { if (a.level != b.level) return a.level < b.level; return a.index > b.index; } int main() { int n, have[100] = {0}, root = 0; cin >> n; for (int i = 0; i < n; i++) { a[i].id = i; string l, r; cin >> l >> r; if (l != "-") { a[i].l = stoi(l); have[stoi(l)] = 1; } else { a[i].l = -1; } if (r != "-") { a[i].r = stoi(r); have[stoi(r)] = 1; } else { a[i].r = -1; } } while (have[root] == 1) root++; dfs(root, 0, 0); vector<node> v2(v1); sort(v2.begin(), v2.end(), cmp); for (int i = 0; i < v2.size(); i++) { if (i != 0) cout << " "; cout << v2[i].id; } cout << endl; for (int i = 0; i < v1.size(); i++) { if (i != 0) cout << " "; cout << v1[i].id; } return 0; }

我的

#include<bits/stdc++.h> using namespace std; const int maxn = 20; struct node{ int l,r; }nodes[maxn]; int n, rt; char l[10],r[10]; int stoi(char *s){ int len = strlen(s); int ans = 0; for(int i=0;i<len;i++){ ans = ans * 10 + s[i]-'0'; } return ans; } vector<int> level; void bfs(){ queue<int> q; q.push(rt); while(!q.empty()){ int i = q.front(); q.pop(); level.push_back(i); if(nodes[i].l != -1) q.push(nodes[i].l); if(nodes[i].r != -1) q.push(nodes[i].r); } } vector<int> in; void dfs(int root){ if(root == -1) return; dfs(nodes[root].l); in.push_back(root); dfs(nodes[root].r); } vector<int> tmp; int main(){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%s %s",l,r); if(strcmp(l,"-")==0) nodes[i].r = -1; else{ int num = stoi(l); tmp.push_back(num); nodes[i].r = num; } if(strcmp(r,"-")==0) nodes[i].l = -1; else{ int num = stoi(r); tmp.push_back(num); nodes[i].l = num; } } bool flag; for(int i=0;i<n;i++){ flag = false; for(int j=0;j<tmp.size();j++){ if(tmp[j] == i){ flag = true; break; } } if(!flag) rt = i; } bfs(); dfs(rt); for(int i=0;i<level.size();i++){ if(i==0) printf("%d",level[i]); else printf(" %d",level[i]); } printf("\n"); for(int i=0;i<in.size();i++){ if(i==0) printf("%d",in[i]); else printf(" %d",in[i]); } printf("\n"); } 

转载于:https://www.cnblogs.com/doragd/p/11288612.html

本文来源weixin_30595035,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/29556

发表评论