动态表白网站制作叶涛网站推广优化
重建二叉树
引言
问题：现有二叉树的后序遍历序列与中序遍历序列，能否求原二叉树？
答案是肯定的，并且前序与中序也可以得到原二叉树。
本文就如何使用这两种序列组合如何重建二叉树进行讨论。
首先，定义二叉树的遍历。
二叉树的遍历
对于一个二叉树的遍历，有以下原则：
- 遇到一个根节点，先访问左节点，再访问右节点而前，后，中序遍历分别指根节点在访问左右节点之前，之间，之后。
如何重建？
那么根据二叉树遍历的定义，对一个最简单的只有一个根节点与左右节点的二叉树，来尝试重建。
设一个二叉树为下图左所示，它的前，中，后序遍历序列分别如下图右所示：
假设我们只知道后序与中序，如何重建呢？
- 显然，后序的最后一个数字就是根节点，也就是 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]);elseinright.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/#/
想看到我的更多更新的话，很乐意你关注我！
你是谁？
欢迎在文后留下评论，一起讨论，欢迎认识新朋友。
如果你也有博客，在分享你的东西，欢迎交流、友链(见博客底部)。
下一篇见~