Tree——Construct Binary Tree from Inorder and Postorder Traversal

问题描述：

给定树的中序和后序遍历，构建二叉树。

解题思路：

可以先举一个具体的例子，比如： inorder：74258136       postorder：74852631 根据后序遍历的特性，postorder中的最后一个数字肯定是整棵树的根。然后在中序遍历中找到根所在的位置，左边就是根的左子树的中序遍历，右边就是根的右子树的中序遍 历。根据根的左右子树的中序遍历的序列长度，可以确定在postorder中哪一段是根的左子树的后序遍历，哪一段是根的右子树的后序遍历。 由此，我们可以递归的调用buildTree函数，然而在编程的时候我遇到了一点问题： 首先是我采用4个vector去储存左右子树的中后序遍历，然后编译器报告了错误：std::bad_alloc  也就是说无法分配所请求的空间。这个方法的空间复杂度太高了，所以不能采用 4个vector去储存左右子树的中后序遍历。所以写了一个辅助函数，多加了4个参数，用来记录中后序序列的开始位置和结束位置。

源代码如下：

class Solution {

public:     TreeNode* helpbuildTree(vector<int>& inorder,int bgn0,int end0,vector<int>& postorder,int bgn1,int end1)     {         if(bgn0>end0||bgn1>end1) return NULL;         TreeNode* root = new TreeNode(postorder[end1]);         int i;         for(i=bgn0;i<=end0;i++)         {             if(postorder[end1]==inorder[i]) break;         }         root->left=helpbuildTree(inorder,bgn0,i-1,postorder,bgn1,bgn1+i-1-bgn0);         root->right=helpbuildTree(inorder,i+1,end0,postorder,bgn1+i-bgn0,end1-1);         return root;     }     TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {         if(inorder.empty()||postorder.empty()) return NULL;         return helpbuildTree(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1);     } };