题解 | 先序遍历、中序遍历和后序遍历

#include <iostream>
#include <vector>

using namespace std;

struct Node {
	int left;
	int right;
};

int n;
bool in_degree[100005];

void pre_order(int root, vector<Node>& tree) {
	if (!root) return;
	cout << root << " ";
	pre_order(tree[root].left, tree);
	pre_order(tree[root].right, tree);
}
void in_order(int root, vector<Node>& tree) {
	if (!root) return;
	in_order(tree[root].left, tree);
	cout << root << " ";
	in_order(tree[root].right, tree);
}
void post_order(int root, vector<Node>& tree) {
	if (!root) return;
	post_order(tree[root].left, tree);
	post_order(tree[root].right, tree);
	cout << root << " ";
}

//不知道有没有什么更好的方式存储树的信息
int main() {
	cin >> n;
	vector<Node> tree(n + 1);
	int v1, v2;
	for (int i = 0; i < n - 1; i++) {
		cin >> v1 >> v2;
		in_degree[v2] = true;
		int subling = max(tree[v1].left, tree[v1].right);
		if (subling) {
			int left, right;
			right = max(subling, v2);
			left = min(subling, v2);			 
			tree[v1].left = left;
			tree[v1].right = right;
		} else {
			if (v1 > v2) tree[v1].right = v2;
			else tree[v1].left = v2;
		}
	}
	int root;
	for (int i = 1; i <= n; i++) {
		if(!in_degree[i]) root = i;  
	}
	pre_order(root, tree);
	cout << endl;
	in_order(root, tree);
	cout << endl;
	post_order(root, tree);
	cout << endl;
}