10.6（ 105. 从前序与中序遍历序列构造二叉树 106. 从中序与后序遍历序列构造二叉树 ）

本文主要是介绍10.6（ 105. 从前序与中序遍历序列构造二叉树 106. 从中序与后序遍历序列构造二叉树 ），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

105. 从前序与中序遍历序列构造二叉树（通过）

思路：递归构造

效率：86.85%

程序代码（完整版）：

#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<sstream>
#include<stack>//引入数据结构堆栈
using namespace std;
//105. 从前序与中序遍历序列构造二叉树
//思路：递归struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int n = preorder.size();return Haha(0, n-1, preorder, 0, n-1,inorder);}TreeNode* Haha(int a, int b, vector<int>& preorder, int c, int d, vector<int>& inorder) {if (a > b) return NULL;else {TreeNode* root = new TreeNode(preorder[a]);//首先创建一个根部节点int a1, b1, c1, d1, a2, b2, c2, d2;for (int i = c; i <= d; i++) {if (inorder[i] == preorder[a]) {a1 = a + 1;b1 = a + i - c;c1 = c;d1 = i - 1;a2 = a + i - c + 1;b2 = b;c2 = i + 1;d2 = d;}}root->left = Haha(a1, b1, preorder, c1, d1, inorder);root->right = Haha(a2, b2, preorder, c2, d2, inorder);return root;}}};void Traverse(vector<int> &result,TreeNode *root) {if (root == NULL);//这属于什么也不干else {result.push_back(root->val);Traverse(result,root->left);Traverse(result,root->right);}}int main() {Solution bb;int n;cin >> n;vector<int> a(n);vector<int> b(n);for (int i = 0; i < n; i++) {cin >> a[i] >> b[i];}TreeNode *root = bb.buildTree(a,b);vector<int> result;Traverse(result,root);for (int i = 0; i < n; i++) {cout << result[i];}return 0;}

前序遍历：根左右
中序遍历：左根右
后序遍历：左右根

106. 从中序与后序遍历序列构造二叉树

思路：和上面题目的思路一样

效率：79.52%

程序代码：

#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<sstream>
#include<stack>//引入数据结构堆栈
using namespace std;
//105. 从前序与中序遍历序列构造二叉树
//思路：递归struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int n = postorder.size();return Haha(0, n-1, postorder, 0, n-1,inorder);}TreeNode* Haha(int a, int b, vector<int>& postorder, int c, int d, vector<int>& inorder) {if (a > b) return NULL;else {TreeNode* root = new TreeNode(postorder[b]);//首先创建一个根部节点int a1, b1, c1, d1, a2, b2, c2, d2;for (int i = c; i <= d; i++) {if (inorder[i] == postorder[b]) {a1 = a;b1 = a+i-1-c;c1 = c;d1 = i - 1;a2 = b+i-d;b2 = b-1;c2 = i + 1;d2 = d;}}root->left = Haha(a1, b1, postorder, c1, d1, inorder);root->right = Haha(a2, b2, postorder, c2, d2, inorder);return root;}}};void Traverse(vector<int> &result,TreeNode *root) {if (root == NULL);//这属于什么也不干else {result.push_back(root->val);Traverse(result,root->left);Traverse(result,root->right);}}int main() {Solution bb;int n;cin >> n;vector<int> a(n);vector<int> b(n);for (int i = 0; i < n; i++) {cin >> a[i] >> b[i];}TreeNode *root = bb.buildTree(a,b);vector<int> result;Traverse(result,root);for (int i = 0; i < n; i++) {cout << result[i];}return 0;}

补充知识点：

关于map和makepair，最快的方法使用的有map何makepair，用时8ms，而我的程序用时16ms，大家的思路整体上其实是差不多的。

最好的程序如下：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:
TreeNode* iterBuild(vector<int>& inorder, int is, int ie,vector<int>& postorder, int ps, int pe, unordered_map<int ,int> &mapList)
{if(is > ie || ps>pe)return NULL;int ri = mapList[postorder[pe]];TreeNode * root = new TreeNode(postorder[pe]);root->left = iterBuild(inorder, is, ri-1, postorder, ps, ps+ri-is-1, mapList);root->right = iterBuild(inorder, ri+1, ie, postorder, ps+ri-is, pe-1, mapList);return root;
}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
{if(inorder.size()!=postorder.size() || !inorder.size() || !postorder.size())return NULL;unordered_map<int ,int> mapList;for(int i=0; i<inorder.size(); i++)mapList.insert(make_pair(inorder[i], i));return iterBuild(inorder, 0, inorder.size()-1, postorder, 0, postorder.size()-1, mapList);
}
};

所以，map其实就相当于是使中序遍历序列的元素和下标一一对应，是一个一对一的hash表，不需要再使用for循环依次寻找。节省了时间。

这篇关于10.6（ 105. 从前序与中序遍历序列构造二叉树 106. 从中序与后序遍历序列构造二叉树 ）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---