leetcode-1006 Construct Binary Tree from Inorder and Postorder Traversal-白红宇

leetcode-1006 Construct Binary Tree from Inorder and Postorder Traversal

阅读量：4685 次

发布时间：2019-06-09

本文共 2484 字，大约阅读时间需要 8 分钟。

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
      
       & inorder, vector
       
        & 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

left;29 for(int i=0;i

right;32 for(int i=flag+1;i

left1;45 for(int i=0;i

right1;48 for(int i=flag1;i

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
      
       & inorder, vector
       
        & postorder) {13         return helper(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1);14     }15     16     TreeNode* helper(vector
        
         & inorder,int begin1,int end1,vector
         
          & 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 };