1127. ZigZagging on a Tree (30)

2019-11-06 07:27:52

字体：大中小

来源：转载

供稿：网友

按照中序后序建好树，然后按题目要求输出

#include<iostream>#include<vector>#include<algorithm>using namespace std;struct node { int data; node *l, *r; node() { l = r = NULL; }};vector<node> all;int N;int m[50], n[50];int FindN(int e){ for (int t = 0;t < N;t++) if (all[t].data == e) return t; return 0;}void change(int a, int b, int c, int d)//建树{ if (a >= b || c >= d) return; int pos = find(m, m + N, n[d]) - m-a; if(a+pos>a) all[m[a + pos]].l = &all[n[c+ pos-1]]; if(a+pos<b) all[m[a + pos]].r = &all[n[d - 1]]; change(a, a + pos - 1, c, c + pos - 1); change(a + pos + 1, b, c + pos, d - 1);}int main(){ cin >> N; all.resize(N); for (int t = 0;t < N;t++) { cin >> all[t].data; m[t] = t; } for (int t = 0;t < N;t++) { cin >> n[t]; n[t] = FindN(n[t]); } change(0, N - 1, 0, N - 1); node *root = &all[n[N - 1]];//以下为输出 vector<node *> aa, bb; if (root->l) aa.push_back(root->l); if (root->r) aa.push_back(root->r); cout << root->data; int flag = -1; while (!aa.empty() || !bb.empty()) { flag *= -1; switch (flag) { case 1: for (int t = 0;t < aa.size();t++) { if (aa[t]->l) bb.push_back(aa[t]->l); if (aa[t]->r) bb.push_back(aa[t]->r); cout << " " << aa[t]->data; } aa.clear(); break; case -1: for (int t = 0;t < bb.size();t++) { if (bb[t]->l) aa.push_back(bb[t]->l); if (bb[t]->r) aa.push_back(bb[t]->r); } for (int t = bb.size() - 1;t >= 0;t--) cout << " " << bb[t]->data; bb.clear(); break; } } cout << endl;}

上一篇：定义动态数组

下一篇：Ubuntu16.04编译Caffe遇到的问题及解决办法