当前位置： 首页 > news >正文

已知前、中、后序中两种遍历结果以重建二叉树

news 2026/4/20 15:51:33

已知前、中、后序中两种遍历结果以重建二叉树

当知道前序遍历、中序遍历、后序遍历中的两种遍历方式，就能够反推出二叉树的结构了。
但是要注意一点：已知前序遍历&后序遍历结果时，二叉树不能有节点的度为1！！！
提醒： 此处默认二叉树节点存储的值为int类型，其他类型，如char等可以将vector换为string等
例题：遍历问题，美国血统

一、已知前&中序遍历结果

// 对应洛谷：https://www.luogu.com.cn/problem/P1827
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;struct Node
{int val;Node *l, *r;Node(int x) : val(x), l(nullptr), r(nullptr) {}
};class BinaryTreeBuilder
{
private:unordered_map<int, int> inorderMap; // 存储中序遍历中各元素的索引位置int preorderIndex;                  // 前序遍历的当前索引public:// 主函数，依据中序与前序遍历构建二叉树Node* buildTree(vector<int>& preorder, vector<int>& inorder){for (int i = 0; i < (int)inorder.size(); i++) inorderMap[inorder[i]] = i;preorderIndex = 0;return buildHelper(preorder, 0, inorder.size()-1);}private:// 递归辅助函数Node* buildHelper(vector<int>& preorder, int inorderStart, int inorderEnd){if (inorderStart > inorderEnd) return NULL;// 前序遍历的当前元素即为根节点int rootVal = preorder[preorderIndex++];Node *root = new Node(rootVal);// 在中序遍历中找到根节点的位置int rootIdx = inorderMap[rootVal];// 构建左、右子树（递归）root->l = buildHelper(preorder, inorderStart, rootIdx-1); // 中序遍历中在根节点前的都属于左子树root->r = buildHelper(preorder, rootIdx+1, inorderEnd);   // 在后面的是右子树部分return root;}public:// 销毁树void destroyTree(Node *root){if (root == NULL) return;destroyTree(root->l);destroyTree(root->r);delete root;}// 中序遍历验证（左-根-右）void inOrder(Node *root){if (root == NULL) return;inOrder(root->l);cout << root->val << " ";inOrder(root->r);}// 前序遍历验证（根-左-右）void preOrder(Node *root){if (root == NULL) return;cout << root->val << " ";preOrder(root->l);preOrder(root->r);}// 后序遍历（左-右-根）void postOrder(Node *root){if (root == NULL) return;postOrder(root->l);postOrder(root->r);cout << root->val << " ";}
};int main()
{// 示例：根据给定的中序和前序遍历构建二叉树vector<int> preorder = {3, 9, 20, 15, 7};  // 前序遍历结果vector<int> inorder = {9, 3, 15, 20, 7};   // 中序遍历结果BinaryTreeBuilder builder;Node* root = builder.buildTree(preorder, inorder);cout << "构建的二叉树遍历结果：" << endl;cout << "前序遍历: ";builder.preOrder(root);cout << endl;cout << "中序遍历: ";builder.inOrder(root);cout << endl;cout << "后序遍历: ";builder.postOrder(root);cout << endl;builder.destroyTree(root);root = NULL;cout << "二叉树销毁完毕！" << endl;return 0;
}

二、已知前&后序遍历结果

注意：二叉树不能有节点的度为1！！！
遍历问题这道题是已知前、后序遍历求有多少种中序遍历结果，中序遍历中度等于1的节点是影响结果的因素，这个也是为什么在已知前、中、后序中两种遍历结果以重建二叉树中设置度不等于1。看了题解知道了一个知识点：前序中出现AB，后序中出现BA，则这个节点只有一个儿子。而这样的话只要找个度为1的节点数n，那么结果就是pow(2, n+1)。但是我们答题的时候一般使用找AB, BA的方法，使用substr(i, 2)截取AB，reverse得到BA，再find。

// 后序遍历的最后一个元素是根节点
// 但是这要求不能有度为1的节点（这不就是哈夫曼树嘛）
/*
解决方法：
1. 前序遍历的第一个元素是树的根节点
2. 后序遍历的最后一个元素也是树的根节点
3. 前序遍历中根节点之后的第一个元素通常是左子树的根节点（如果存在左子树）
4. 在后序遍历中找到这个左子树根节点的位置，就可以划分左右子树的范围
*/
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;struct Node
{int val;Node *l, *r;Node(int x) : val(x), l(nullptr), r(nullptr) {}
};class BuildTree
{
private:unordered_map<int, int> postorderMap;int preorderIndex;public:Node *build(vector<int> preorder, vector<int> postorder){for (int i = 0; i < (int)postorder.size(); i++) postorderMap[postorder[i]] = i;preorderIndex = 0;return buildHelper(preorder, 0, postorder.size()-1);}private:Node *buildHelper(vector<int> preorder, int postStart, int postEnd){if (postStart > postEnd || preorderIndex >= (int)preorder.size()) return NULL;int rootVal = preorder[preorderIndex++];Node *root = new Node(rootVal);if (postStart == postEnd) return root; // 只有一个节点，则直接返回// 在后序遍历中找到左子树根节点的位置int lRootVal = preorder[preorderIndex];int lRootIdx = postorderMap[lRootVal];root->l = buildHelper(preorder, postStart, lRootIdx);root->r = buildHelper(preorder, lRootIdx+1, postEnd-1);return root;}public:// 销毁树void destroyTree(Node *root){if (root == NULL) return;destroyTree(root->l);destroyTree(root->r);delete root;}// 中序遍历验证（左-根-右）void inOrder(Node *root){if (root == NULL) return;inOrder(root->l);cout << root->val << " ";inOrder(root->r);}// 前序遍历验证（根-左-右）void preOrder(Node *root){if (root == NULL) return;cout << root->val << " ";preOrder(root->l);preOrder(root->r);}// 后序遍历（左-右-根）void postOrder(Node *root){if (root == NULL) return;postOrder(root->l);postOrder(root->r);cout << root->val << " ";}
};int main()
{// 示例：根据给定的前序和后序遍历构建二叉树vector<int> preorder = {1, 2, 4, 5, 3, 6, 7};   // 前序遍历结果vector<int> postorder = {4, 5, 2, 6, 7, 3, 1};  // 后序遍历结果BuildTree builder;Node* root = builder.build(preorder, postorder);cout << "根据前序和后序遍历重建的二叉树：" << endl;cout << "前序遍历: ";builder.preOrder(root);cout << endl;cout << "中序遍历: ";builder.inOrder(root);cout << endl;cout << "后序遍历: ";builder.postOrder(root);cout << endl;// 释放内存builder.destroyTree(root);root = nullptr;cout << "二叉树内存已释放！" << endl;return 0;
}

三、已知中&后序遍历结果

// 这个和已知前&中差不多，因为只要找到根节点——后序遍历的最后一个元素，再将中序遍历中左右子树（根节点的前后）递归创建拼接即可
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;struct Node
{int val;Node *l, *r;Node(int x) : val(x), l(nullptr), r(nullptr) {}
};class Tree
{
private:unordered_map<int, int> inorderMap;int postorderIndex;public:Node *build(vector<int> inorder, vector<int> postorder){for (int i = 0; i < (int)inorder.size(); i++) inorderMap[inorder[i]] = i;postorderIndex = postorder.size() - 1;return buildHelper(postorder, 0, inorder.size()-1);}private:Node *buildHelper(vector<int> postorder, int inorderStart, int inorderEnd){if (inorderStart > inorderEnd) return NULL;int rootVal = postorder[postorderIndex--];Node *root = new Node(rootVal);int rootIdx = inorderMap[rootVal];root->r = buildHelper(postorder, rootIdx+1, inorderEnd);root->l = buildHelper(postorder, inorderStart, rootIdx-1);return root;}public:// 销毁树void destroyTree(Node *root){if (root == NULL) return;destroyTree(root->l);destroyTree(root->r);delete root;}// 中序遍历验证（左-根-右）void inOrder(Node *root){if (root == NULL) return;inOrder(root->l);cout << root->val << " ";inOrder(root->r);}// 前序遍历验证（根-左-右）void preOrder(Node *root){if (root == NULL) return;cout << root->val << " ";preOrder(root->l);preOrder(root->r);}// 后序遍历（左-右-根）void postOrder(Node *root){if (root == NULL) return;postOrder(root->l);postOrder(root->r);cout << root->val << " ";}
};int main()
{// 示例：根据给定的中序和前序遍历构建二叉树vector<int> preorder = {9, 3, 15, 20, 7};  // 中序遍历结果vector<int> inorder = {9, 15, 7, 20, 3};   // 后序遍历结果Tree builder;Node* root = builder.build(preorder, inorder);cout << "构建的二叉树遍历结果：" << endl;cout << "前序遍历: ";builder.preOrder(root);cout << endl;cout << "中序遍历: ";builder.inOrder(root);cout << endl;cout << "后序遍历: ";builder.postOrder(root);cout << endl;builder.destroyTree(root);root = NULL;cout << "二叉树销毁完毕！" << endl;return 0;
}
http://www.jsqmd.com/news/671943/

相关文章：

  • 手把手教你为STM32移植AK09918磁力计驱动（附Linux驱动对比与源码）
  • 用树莓派控制电源？PyVISA+SCPI硬件自动化全攻略（2024新版）
  • 2026年全国景观雾森系统TOP5品牌实力榜单 - 深度智识库
  • 别再只用MODIS了！Landsat、SPOT-VGT等NDVI历史数据宝藏库盘点与实战拼接教程
  • 解密音乐格式壁垒：Unlock Music浏览器端音频转换方案深度解析
  • MySQL 事务隔离与锁机制详解
  • CodeBuddy Code CLI 快速上手：从安装到第一次对话
  • Winhance中文版终极指南：5步快速优化Windows系统性能
  • 2026届必备的十大降AI率方案推荐
  • 终极指南：3步掌握QQ音乐文件解密，qmcdump让你的音乐无处不在
  • 手把手教你用geopandas和mgwr分析城市POI：以南京小区分布为例
  • 从零搭建到日常维护：一份给Hexo+GitHub Pages新手的保姆级指令清单
  • 通俗易懂讲透 SARSA：强化学习 On-Policy 经典算法
  • OpenPLC Editor技术解析：开源工业自动化的模块化架构与标准化实践
  • Linux运维必备：手把手教你用OMSA命令行监控Dell PowerEdge服务器硬件状态
  • 如何快速构建繁体中文手写识别系统：5步完整指南
  • Windows 10安卓子系统完整教程：无需升级Win11的终极解决方案
  • 告别RNN！用PyTorch复现轻量级车牌识别LPRNet（附完整训练与避坑指南）
  • 别只盯着S参数！用HFSS快速扫频+场后处理，5分钟查看任意频点的电磁场分布
  • TS3380,TS332,TS3480,G3810,TS3300,ts3440,TS3370,TS8380打印机废墨垫清零软件,错误代码5B00,P07,E08，1700，5b04，亲测有效。
  • PMP题库_10_相关方管理
  • Windows Cleaner终极指南：三步告别C盘爆红的免费系统清理神器
  • 告别C++！我用Rust和Qt 5.14.2重构了一个小工具，聊聊混合编程的真实体验
  • FanControl传感器问题终极指南：如何快速解决风扇控制异常并优化系统散热 [特殊字符]
  • 第4篇：继承基础——单继承、super()与方法重写
  • 开发必看！5款主流Python依赖安全扫描工具深度对比，选型不再难
  • OpCore-Simplify终极指南：三步快速配置黑苹果EFI，零基础也能轻松上手
  • 告别单打独斗：用Nash Q-Learning算法搞定多智能体博弈（附Python代码示例）
  • 手把手教你用STM32F103C8T6和ESP8266搭建智能温室监控（附源码和原子云配置）
  • 3个维度重构数字阅读：从信息消费到知识创造的思维跃迁