P1827 [USACO3.4] 美国血统 American Heritage（前序 + 中序 生成后序）

P1827 [USACO3.4] 美国血统 American Heritage（前序 + 中序 生成后序）

一、前言

二叉树入门题。涉及到树的基本知识、树的结构、树的生成。
本文从会从结构，到完成到，优化。

二、基础知识

Ⅰ、二叉树的遍历

• 前序遍历： 根左右
• 中序遍历： 左根右
• 后序遍历： 左右根

通过上面的观察，可得根在那，就是什么方式的遍历

Ⅱ、二叉树的结构

二叉树的结构：节点值 + 左节点指针 + 右节点指针

// c++的结构体写法
struct node {
	char val;
	node *left;
	node *right;
	node() : val(0), left(nullptr), right(nullptr){}
    node(int val) : val(val), left(nullptr), right(nullptr){}
    node(int val, node *left, node *right) : val(val), left(left), right(right){}
};
// c语言结构体写法
struct node {
	char val;
	struct node *left;
	struct node *right;
	node() : val(0), left(NULL), right(NULL){}
    node(int val){
    	val = val;
    	left = NULL;
    	right = NULL;
    {
    node(int val, struct node *left, struct node *right) {
		val = val;
    	left = left;
    	right = right;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

三、直接思路

通过 前序 + 中序 直接生成 树。然后再前序遍历（可以过）
现在的问题，就变成了。怎么生成树了。
估计大家在学习数据结构，二叉树这一章节中。老师肯定讲过手写这个题（通过前序或后序找到根节点，然后把中序分成两部分，左子树，右子树）。但是现在怎么把他变成代码呢？

#include 
using namespace std;

struct node {
	char val;
	node *left;
	node *right;
	node() : val(0), left(nullptr), right(nullptr){}
	node(char x) : val(x), left(nullptr), right(nullptr){}
	node(char x, node *left, node *right) : val(x), left(left), right(right){}
};
/*
s1 中序
[inorderBegin， inorderEnd）
s2 前序
[preorderBegin， preorderEnd）
上述就是现在树的范围
再分割子树的范围就可以了
明白范围！！！左端点可取，右端点不可取
*/
node *traversal(string s1, int inorderBegin, int inorderEnd, string s2, int preorderBegin, int preorderEnd) {
	if (preorderEnd == preorderBegin) return nullptr;
	char val = s2[preorderBegin];
	node *root = new node(val);

	if (preorderEnd - preorderBegin == 1) return root;

	int delimiterIndex; // 左右子树的分割点
	for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
		if (s1[delimiterIndex] == val) break;
	}
	
	// 左子树
	// 中序
	int leftInorderBegin = inorderBegin;
	int leftInorderEnd = delimiterIndex;
	// 前序
	int leftPreorderBegin = preorderBegin + 1;
	int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin;

	// 右子树
	int rightInorderBegin = delimiterIndex + 1;
	int rightInorderEnd = inorderEnd;
	int rightPreorderBegin = preorderBegin + delimiterIndex - inorderBegin + 1;
	int rightPreorderEnd = preorderEnd;

	root->left = traversal(s1, leftInorderBegin, leftInorderEnd, s2, leftPreorderBegin, leftPreorderEnd);
	root->right = traversal(s1, rightInorderBegin, rightInorderEnd, s2, rightPreorderBegin, rightPreorderEnd);
	return root;
}

void dfs(node *root) {
	if (!root) return ;
	dfs(root->left);
	dfs(root->right);
	cout << root->val;
}


int main() {
	node *tree;
	string s1, s2;
	cin >> s1 >> s2;
	tree = traversal(s1, 0, s1.size(), s2, 0, s2.size());
	dfs(tree);
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

四、优化

通过上面可以发现，他在生成树的过程中，就是经行的后续遍历。所以不用直接生成树。

#include 
using namespace std;

void traversal(string s1, int inorderBegin, int inorderEnd, string s2, int preorderBegin, int preorderEnd) {
	if (preorderEnd == preorderBegin) return;
	char val = s2[preorderBegin];

	int delimiterIndex; // 左右子树的分割点
	for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
		if (s1[delimiterIndex] == val) break;
	}
	
	// 左子树
	// 中序
	int leftInorderBegin = inorderBegin;
	int leftInorderEnd = delimiterIndex;
	// 前序
	int leftPreorderBegin = preorderBegin + 1;
	int leftPreorderEnd = preorderBegin + 1 + delimiterIndex - inorderBegin;

	// 右子树
	int rightInorderBegin = delimiterIndex + 1;
	int rightInorderEnd = inorderEnd;
	int rightPreorderBegin = preorderBegin + delimiterIndex - inorderBegin + 1;
	int rightPreorderEnd = preorderEnd;

	traversal(s1, leftInorderBegin, leftInorderEnd, s2, leftPreorderBegin, leftPreorderEnd);
	traversal(s1, rightInorderBegin, rightInorderEnd, s2, rightPreorderBegin, rightPreorderEnd);
	cout << val;
}

int main() {
	string s1, s2;
	cin >> s1 >> s2;
	traversal(s1, 0, s1.size(), s2, 0, s2.size());
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

五、相关题目

• LeetCode 105. 从前序与中序遍历序列构造二叉树
• LeetCode 106. 从中序与后序遍历序列构造二叉树

六、最后

创作不易，留个赞，鼓励一下把！