当前位置: 代码迷 >> 综合 >> PAT1020 Tree Traversals (25)(中序后序遍历生成树)
  详细解决方案

PAT1020 Tree Traversals (25)(中序后序遍历生成树)

热度:86   发布时间:2024-01-16 13:24:26.0

题目很简单,就是给出树的中序和后序遍历,要求输出层序遍历,记录一下主要是因为之前这块一直懒得写,一直没写过

#include<bits/stdc++.h>
#define INF 0x6ffff
using namespace std;struct node {int data;node *left, *right;
};
int n;
int postOrder[35],inOrder[35];node* buildTree(int l, int r, int ll, int rr){if (l > r || ll > rr) {return nullptr;}node *temp = new node;int d = postOrder[r];int pos;for (int i = ll; i <= rr; i++) {if (d == inOrder[i]) {pos = i;break;}}	int numLeft = pos - ll;int numRight = rr - pos;temp->data = d;temp->left = buildTree(l, l + numLeft - 1, ll, pos - 1);temp->right = buildTree(r - numRight, r-1, pos + 1, rr);return temp;
}void printTree(node *front) {queue<node*> q;q.push(front);while (!q.empty()) {node *t = q.front(); q.pop();if (!t) continue;if (t == front)printf("%d", t->data);elseprintf(" %d", t->data);q.push(t->left);q.push(t->right);}
}int main() {cin >> n;for (int i = 1; i <= n; i++)cin >> postOrder[i];for (int i = 1; i <= n; i++)cin >> inOrder[i];node *front = buildTree(1, n, 1, n);printTree(front);return 0;
}

 

 

 

  相关解决方案