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

Note:

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

 

C++实现代码：

#include
     
      #include
      
       #include
       
        using namespace std;//Definition for binary treestruct TreeNode{    int val;    TreeNode *left;    TreeNode *right;    TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {public:    TreeNode *buildTree(vector
        
          &inorder, vector
         
           &postorder) {        TreeNode *root=NULL;        root=build(inorder.begin(),inorder.end(),postorder.begin(),postorder.end());        return root;    }    TreeNode *build(vector
          
           ::iterator ibegin,vector
           
            ::iterator iend,vector
            
             ::iterator pbegin,vector
             
              ::iterator pend) { TreeNode *root=NULL; if(pbegin==pend||ibegin==iend) return NULL; auto it=ibegin; auto tmp=pend-1; while(it!=iend) { if(*it==*tmp) break; it++; } root=new TreeNode(*it); int len=it-ibegin; root->left=build(ibegin,it,pbegin,pbegin+len); root->right=build(it+1,iend,pbegin+len,pend-1); return root; } void preorder(TreeNode *root) { if(root) { cout<
              
               val<<" "; preorder(root->left); preorder(root->right); } } void inorder(TreeNode *root) { if(root) { inorder(root->left); cout<
               
                val<<" "; inorder(root->right); } } void postorder(TreeNode *root) { if(root) { postorder(root->left); postorder(root->right); cout<
                
                 val<<" "; } }};int main(){ vector
                 
                   posorder={ 4,5,2,6,7,3,1}; vector
                  
                    inorder={ 4,2,5,1,6,3,7}; Solution s; TreeNode *root=s.buildTree(inorder,posorder); s.preorder(root); cout<
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

运行结果：