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;}
};

三、直接思路

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

#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;
}

五、相关题目

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

六、最后

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