[数据结构与算法]Advanced1020 Tree Traversals:基础数组搞定二叉树遍历问题！

问题概述：
提供二叉树后续与中序遍历，求层序遍历。
思路：希望通过数组而不是结构链表来构建二叉树，从而减少代码量。
算法核心：设父节点序号为n，则左右子节点序号分别为2n+1和2n+2；

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<vector<int> >tree;
vector<int>post, in;
int N;

void trav(int pb,int ib,int node,int len)
{
	if (pb < 0 || ib < 0 || len < 0)return;
	tree.push_back({ node, post[pb+len] });
	if (len == 0)return;

	int i = ib;
	while (in[i] != post[pb+len])++i;
	trav(pb, ib, node * 2 + 1, i - ib - 1);
	trav(pb + i - ib, i + 1, node * 2 + 2, len - i + ib - 1);
}
bool cmp(vector<int>a, vector<int>b)
{
	return a[0] < b[0];
}

int main()
{
	//input;
	cin >> N;
	int n;
	for (int i = 0;i < N;i++){
		cin >> n;post.push_back(n);
	}
	for (int i = 0;i < N;i++){
		cin >> n;in.push_back(n);
	}
	//work;
	trav(0, 0, 0, N-1);//trav(post.begin(), in.begin(), node, len);
	sort(tree.begin(), tree.end(), cmp);
	cout << tree[0][1];
	for (int i = 1;i < tree.size();i++){
		cout << ' ' << tree[i][1];
	}

	return 0;
}

代码并没有经过太多优化，观察其他解答，发现map能够进一步简化节点与层级的对应关系，且map可以自排序，甚至不需要sort。