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;
}
};
三、直接思路
通过 前序 + 中序 直接生成 树。然后再前序遍历（可以过）
现在的问题，就变成了。怎么生成树了。
估计大家在学习数据结构，二叉树这一章节中。老师肯定讲过手写这个题（通过前序或后序找到根节点，然后把中序分成两部分，左子树，右子树）。但是现在怎么把他变成代码呢？
#include <iostream>
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;
}
四、优化
通过上面可以发现，他在生成树的过程中，就是经行的后续遍历。所以不用直接生成树。
#include <iostream>
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;
}
五、相关题目
六、最后
创作不易，留个赞，鼓励一下把！
