河北邢台沙河疫情最新消息_泰安网页建设_市场营销互联网营销_3小时百度收录新站方法

---

一、leetcode-106

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

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

---

二、题解

1.引库

 #include <iostream>#include <cstdio>#include <cstdlib>#include <queue>#include <stack>#include <algorithm>#include <string>#include <map>#include <set>#include <vector>using namespace std;

2.代码

此时有一个很重的点，就是中序数组大小一定是和后序数组的大小相同的（这是必然）。

class Solution {
public:TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if(postorder.size()==0) return NULL;int rootValue=postorder.back();TreeNode *root=new TreeNode(rootValue);if(postorder.size()==1) return root;int rootIndex=0;for(;rootIndex<inorder.size();rootIndex++){if(inorder[rootIndex]==rootValue) break;}vector<int> leftInorder(inorder.begin(),inorder.begin()+rootIndex);vector<int> rightInorder(inorder.begin()+rootIndex+1,inorder.end());vector<int> leftPostorder(postorder.begin(),postorder.begin()+rootIndex);vector<int> rightPostorder(postorder.begin()+rootIndex,postorder.end()-1);root->left=buildTree(leftInorder,leftPostorder);root->right=buildTree(rightInorder,rightPostorder);return root;}
};

此时应该发现了，如上的代码性能并不好，因为每层递归定义了新的vector（就是数组），既耗时又耗空间，但上面的代码是最好理解的，为了方便读者理解，所以用如上的代码来讲解。

    TreeNode* traversal (vector<int>& inorder, int inorderBegin, int inorderEnd, vector<int>& postorder, int postorderBegin, int postorderEnd) {if (postorderBegin == postorderEnd) return NULL;int rootValue = postorder[postorderEnd - 1];TreeNode* root = new TreeNode(rootValue);if (postorderEnd - postorderBegin == 1) return root;int delimiterIndex;for (delimiterIndex = inorderBegin; delimiterIndex < inorderEnd; delimiterIndex++) {
…return root;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {if (inorder.size() == 0 || postorder.size() == 0) return NULL;// 左闭右开的原则return traversal(inorder, 0, inorder.size(), postorder, 0, postorder.size());}