leetcode-1006 Construct Binary Tree from Inorder and Postorder Traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

题意：根据中序遍历和后序遍历，构建二叉树

思路很清晰，做法很简单，就不讲了。

一开始我写了一个递归的解法，本地测试数据都OK，无奈提交的时候内存超出限制，下面先给出超出内存的代码：

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
13         if(inorder.size()==0)
14         return nullptr;
15         if(inorder.size()==1)
16         return new TreeNode(inorder[0]);
17         int fath=postorder[postorder.size()-1];
18         TreeNode* root=new TreeNode(fath);
19         int flag=-1;
20         for(int i=0;i<inorder.size();i++)
21         {
22             if(inorder[i]==fath)
23             {
24                 flag=i;
25                 break;
26             }
27         }
28         vector<int> left;
29         for(int i=0;i<flag;i++)
30         left.push_back(inorder[i]);
31         vector<int> right;
32         for(int i=flag+1;i<inorder.size();i++)
33         right.push_back(inorder[i]);
34         int flag1=-1;
35         for(int i=0;i<postorder.size();i++)
36         {
37             if(postorder[i]==inorder[flag])
38             {
39                 flag1=i;
40                 break;
41             }
42         }
43         
44         vector<int> left1;
45         for(int i=0;i<flag1;i++)
46         left1.push_back(postorder[i]);
47         vector<int> right1;
48         for(int i=flag1;i<postorder.size()-1;i++)
49         right1.push_back(postorder[i]);
50         
51         root->left=buildTree(left,left1);
52         root->right=buildTree(right,right1);
53         return root;
54     }
55 };

有没有看出问题，没错，就是第28、31、44、47行的代码，每次递归都会产生新的vector数组，所以最后导致内存超出限制。所以改进了一下，新定义一个方法helper来递归，helper里面的实现不再申请新的vector空间，直接在参数inorder和postorder中进行操作，从而避免内存超出限制。下面是accepted的代码：

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
13         return helper(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1);
14     }
15     
16     TreeNode* helper(vector<int>& inorder,int begin1,int end1,vector<int>& postorder,int begin2,int end2)
17     {
18         if(begin1>end1)
19             return nullptr;
20         if(begin1==end1)
21             return new TreeNode(inorder[begin1]);
22         
23         TreeNode* root=new TreeNode(postorder[end2]);
24         int i=begin1;
25         for(;i<=end1;i++)
26         {
27             if(inorder[i]==postorder[end2])
28             break;
29         }
30         int leftlen=i-begin1;
31         
32         root->left=helper(inorder,begin1,begin1+leftlen-1,postorder,begin2,begin2+leftlen-1);
33         root->right=helper(inorder,begin1+leftlen+1,end1,postorder,begin2+leftlen,end2-1);
34         return root;
35     }
36 };