[数据结构与算法]L2-006 树的遍历 (25 分)

题目

题目链接

题解

对先序遍历、后序遍历、中序遍历、层序遍历的理解 + DFS。

由后序遍历和中序遍历得到先序遍历后不知道怎么得到层序遍历了，写了好久的记忆化搜索都没写对，最后扫了一眼大佬的，发现就差一点。还是理解不到位，记忆化搜索是弱项。

代码

#include<bits/stdc++.h>
using namespace std;

vector <int> v;

int a[50], b[50], n, left_val[50], right_val[50]; // left_val[x] 表示值为x的根左子树树根的值 

int dfs (int l1, int r1, int l2, int r2) { // 记忆化搜索 // [l1,r1]表示递归的后序遍历序列的索引范围，[l2,r2]表示递归的中序遍历的索引范围 
	
	if (l1 > r1 || l2 > r2) return 0; // 递归边界 
	
	int root = a[r1], p = l2;	
	while (p <= r2) { // 找到中序遍历中根所在的索引 
		if (b[p] == root) break;
		p ++;
	}
	int left_sum = p - l2; // 左子树节点数 
	left_val[root] = dfs (l1, l1+left_sum-1, l2, p-1); // left_subtree // [l1, l1+left_sum-1] 表示后序遍历序列中左子树的索引范围
	right_val[root] = dfs (l1+left_sum, r1-1, p+1, r2); // right_subtree
	return root;
}

void bfs (int x) {
	queue <int> q;
	q.push (x);
	while (q.size ()) {
		int t = q.front ();
		q.pop ();
		v.push_back (t);
		if (left_val[t]) q.push (left_val[t]);
		if (right_val[t]) q.push (right_val[t]);
	}	
}

int main()
{
	cin >> n;
	for (int i = 1;i <= n;i ++) cin >> a[i];
	for (int i = 1;i <= n;i ++) cin >> b[i];
	
	dfs (1, n, 1, n);
	
	bfs (a[n]);
	
	cout << v[0];
	for (int i = 1;i < v.size();i ++)
	cout << ' ' << v[i];

	return 0;
}