重建二叉树
引言
问题：现有二叉树的后序遍历序列与中序遍历序列，能否求原二叉树？
答案是肯定的，并且前序与中序也可以得到原二叉树。
本文就如何使用这两种序列组合如何重建二叉树进行讨论。
首先，定义二叉树的遍历。
二叉树的遍历
对于一个二叉树的遍历，有以下原则：
- 遇到一个根节点，先访问左节点，再访问右节点
而前，后，中序遍历分别指根节点在访问左右节点之前，之间，之后。
如何重建？
那么根据二叉树遍历的定义，对一个最简单的只有一个根节点与左右节点的二叉树，来尝试重建。
设一个二叉树为下图左所示，它的前，中，后序遍历序列分别如下图右所示：
二叉树遍历
假设我们只知道后序与中序，如何重建呢？
- 显然，后序的最后一个数字就是根节点，也就是 3 是根节点。
- 在中序中找到3，它的左边是左节点，右边是右节点。
- 最终重建到二叉树：根为3，左节点为7，右节点为1
由上方重建过程思考后，可以推广：
对于更复杂的二叉树，将其先看作上图模型的二叉树，重建得到根节点与暂时混乱的左右节点，再递归的将左右节点依次重建为子二叉树，即可完成整个二叉树的重建。
在得到根节点之后，需要在中序遍历序列中寻找根节点的位置，并将中序序列拆分为左右部分。所以要求序列中不能有相同的数字，这是序列可重建二叉树的前提。
编码抽象
将重建思路抽象之后，我们可以得到如下过程来重建二叉树：
定义二叉树节点
struct TreeNode {
int data;
TreeNode* left = NULL;
TreeNode* right = NULL;
};
设有后序序列vector<int> post与中序序列vector<int> in，现在我们将二叉树重建到以TreeNode* node为根节点的二叉树中。
1. 取出post的最后一个数R，则R为二叉树的根节点
2. 在in中寻找R的位置
3. 从R拆分为左右子二叉树的中序序列：inleft、inright
4. 在post中，从左到右取出inleft.size()个数字，其组成的序列为左子二叉树的后序序列postleft
5. 类比4得到右子二叉树的后序序列postright
6. 分别根据inleft与postleft重建左子二叉树到node->left
7. 类比6重建右子二叉树到node->right
实现
void getTree(vector<int> post, vector<int> in, TreeNode* node) {
vector<int> inleft, inright;
vector<int> postleft, postright;
if (post.size() == 0) return;
int rootNum = post[post.size() - 1];
post.pop_back();
node->data = rootNum;
// 将中序遍历拆开
bool flag = false;
for (int i = 0; i < in.size(); i++) {
if (in[i] == rootNum) {
flag = true;
continue;
}
if (!flag)
inleft.push_back(in[i]);
else
inright.push_back(in[i]);
}
// 将后序遍历拆开
for (int i = 0; i < post.size(); i++) {
if (i < inleft.size()) {
postleft.push_back(post[i]);
} else {
postright.push_back(post[i]);
}
}
if (inleft.size() > 0) {
node->left = new TreeNode;
getTree(postleft, inleft, node->left);
}
if (inright.size() > 0) {
node->right = new TreeNode;
getTree(postright, inright, node->right);
}
}
全文完。
我是谁？
我是iimT，大学生，技术宅，计算机科技爱好者，电音小王子。
我的博客：www.iimt.me
我在Weibo：@_iimT
我在B站：https://space.bilibili.com/69824765/#/
想看到我的更多更新的话，很乐意你关注我！
你是谁？
欢迎在文后留下评论，一起讨论，欢迎认识新朋友。
如果你也有博客，在分享你的东西，欢迎交流、友链(本人博客底部可申请)。
下一篇见~
