1.二叉树的三种遍历

例题：

原题链接：luoguB3642二叉树的遍历

知识：

• 三种遍历均是深度优先遍历，左儿子一定比右儿子先遍历，“前中后”是根节点的输出的位置
• 前序遍历：先输出根节点的值，再遍历左儿子 ，最后右儿子
• 中序遍历：先遍历左儿子 ，再输出根节点的值，最后右儿子
• 后序遍历：先遍历左儿子 ，再遍历右儿子 ，最后输出根节

完整代码（纯纯应试码风QAQ）：

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e6 + 10;
vector<int> v[N]; //也可改成int v[N][2]，因为二叉树每个节点最多两个儿子
int n;

void preorder(int x) {
	cout << x << ' ';
	if (v[x][0] != 0)
		preorder(v[x][0]);
	if (v[x][1] != 0)
		preorder(v[x][1]);
}

void inorder(int x) {
	if (v[x][0] != 0)
		inorder(v[x][0]);
	cout << x << ' ';
	if (v[x][1] != 0)
		inorder(v[x][1]);
}

void postorder(int x) {
	if (v[x][0] != 0)
		postorder(v[x][0]);
	if (v[x][1] != 0)
		postorder(v[x][1]);
	cout << x << ' ';
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n; i ++) {
		int l, r;
		cin >> l >> r;
		v[i].push_back(l), v[i].push_back(r);
	}
	preorder(1);
	cout << '\n';
	inorder(1);
	cout << '\n';
	postorder(1);
	cout << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while (t --) {
		solve();
	}
	return 0;
}

2.二叉树的序列化和反序列化

已知中序+前序或后序，可以确定一颗二叉树。但前序+后序，无法确定二叉树

例题1：给前序+中序求后序

原题链接：luoguP1827美国血统

知识：

1.二叉树的前序遍历的第一个节点是根节点
2.一个前序遍历序列由以下三部分组成：
[根节点编号] + [根节点左子树的中序遍历序列] + [根节点右子树的中序遍历序列]
3.类似，一个前中序遍历序列由以下三部分组成：
[根节点左子树的前序遍历序列]+ [根节点编号] + [根节点右子树的前序遍历序列]
4.递归思想

解题思路

1. 求根节点左右子树的大小：到根节点在前序遍历序列的位置 $i$，$i$ 到序列两端点的距离分别是左右子树的大小。记左儿子大小为$sizel$。
2. 根节点的左儿子编号在中序序列的第二个位置，根节点的右儿子编号在中序序列的第 $sizel+2$ 个位置。
3. 处理出左子树、右子树的前序序列和中序序列，递归求解

完整代码（纯纯应试码风）

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e6 + 10;
int n;
string s1, s2;
map<char, pair<char, char>> tree;//map建立二叉树，懒得写结构体

void dfs(int l1, int r1, int l2, int r2) {

	if (l1 > r1 || l2 > r2)
		return;
	int root;
	for (int i = l1; i <= r1; i ++) {
		if (s1[i] == s2[l2]) {
			root = i;
			break;
		}
	}
	int sizel = root - l1, sizer = r1 - root;
	if (sizel > 0)
		tree[s2[l2]].first = s2[l2 + 1];
	else
		tree[s2[l2]].first = 0;

	if (sizer > 0)
		tree[s2[l2]].second = s2[l2 + sizel + 1];
	else
		tree[s2[l2]].second = 0;//空节点不用0表示的话，后序遍历时需要加特判

	dfs(l1, root - 1, l2 + 1, l2 + sizel);
	dfs(root + 1, r1, l2 + sizel + 1, r2);
}

void postorder(char x) {
	if (tree[x].first != 0)
		postorder(tree[x].first);
	if (tree[x].second != 0)
		postorder(tree[x].second);
	cout << x;
}

void solve() {
	cin >> s1 >> s2;
	s1 = "#" + s1;
	s2 = "#" + s2;
	dfs(1, s1.size() - 1, 1, s2.size() - 1);
	postorder(s2[1]);
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while (t --) {
		solve();
	}
	return 0;
}

一个优化（了解）

实际上根本不需要建树，在dfs()函数后直接输出根节点编号即可。

	if (sizer > 0)
		tree[s2[l2]].second = s2[l2 + sizel + 1];
	else
		tree[s2[l2]].second = 0;//空节点不用0表示的话，后序遍历时需要加特判

	dfs(l1, root - 1, l2 + 1, l2 + sizel);
	dfs(root + 1, r1, l2 + sizel + 1, r2);
	//此处直接输出
	cout << s2[l2];
}
/*  这段就用不上了
void postorder(char x) {
	if (tree[x].first != 0)
		postorder(tree[x].first);
	if (tree[x].second != 0)
		postorder(tree[x].second);
	cout << x;
}
*/

例题2：给中序+后序求前序

题目传送门
做法同例题1，可参考luogu题解区的题解

例题3：给前序+后序，问可能构建出二叉树的总数

原题链接：luoguP1229遍历问题

知识：

1.对于只有一个儿子的节点，改变该儿子的位置（左儿子为右儿子，或右儿子改为左儿子），其前序、后序遍历序列均不改变。
2.前序遍历第一个位置是根节点，后序遍历的最后一个节点是根节点
3.类似上午，一个后序遍历序列由以下三部分组成：
[根节点左子树的后序遍历序列]+ [根节点右子树的后序遍历序列]+ [根节点编号]
4.递归思想

解题思路：

1.注意到，每一个只有一个儿子的节点，改变其儿子的位置，可得到两棵前后序相同但中序不同的二叉树。故每一个只有一个儿子的节点，使得答案*2。
2.故求只有一个儿子的节点的数量，注意到，根节点只有一个儿子，当且仅当其前序遍历序列的第二个位置的值等于后序遍历序列倒数第二个位置的值。
3.处理完根节点后，处理出左右子树的前序、后序序列，递归求解

完整代码（纯纯应试码风）

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e6 + 10;
int n;
string s1, s2;
int ans;

void dfs(int l1, int r1, int l2, int r2) {

	if (l1 >= r1 || l2 >= r2)
		return;
	if (s1[l1 + 1] == s2[r2 - 1]) {
		ans ++;
		dfs(l1 + 1, r1, l2, r2 - 1);
	} else {
		int sizel = -1;
		for (int i = l1; i <= r1; i ++) {
			if (s1[i] == s2[r2 - 1]) {
				sizel = i - l1 - 1;
				break;
			}
		}
		dfs(l1 + 1, l1 + sizel, l2, l2 + sizel - 1);
		dfs(l1 + sizel + 1, r1, l2 + sizel, r2 - 1);
	}
}


void solve() {
	cin >> s1 >> s2;
	s1 = "#" + s1;
	s2 = "#" + s2;
	dfs(1, s1.size() - 1, 1, s2.size() - 1);
	cout << pow(2, ans) << '\n';
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while (t --) {
		solve();
	}
	return 0;
}

3.二叉树的建立

1.最权威的建法：使用结构体与指针，参见leetcode：传送门
2.使用STL的快速建法：
map<int,pair<int,int>> v 或 int v[N][2] 实现快速建树