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

Note:

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

常规方法，以中序为主，在中序中查找根，划分成左右两部分递归，注意要记录左部分个数，后续遍历找根需要，这里没有考虑不能建成树的情况

1 /** 2  * Definition for binary tree 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         int m=inorder.size();14         int n=postorder.size();15         if(m==0||n==0||m!=n) return NULL;     //如果m，n不等，一定不对16         17         return build(inorder,0,n-1,postorder,0,n-1);18       19     }20     TreeNode * build(vector
       
         & inorder,int inl,int inr,vector
        
          &postorder,int pol,int por)21     {22 23         if(inl>inr)24         {25             return NULL;26         }27         int value=postorder[por];28         TreeNode * root=new TreeNode(value);29         int i;30         int count=0;                             //记录左部分个数                     31         for(i=inl;i<=inr;i++)32         {33             if(inorder[i]==value)34             {35                 break;36             }37             count++;38         }39         root->left=build(inorder,inl,i-1,postorder,pol,pol+count-1);                   //注意count-140         root->right=build(inorder,i+1,inr,postorder,pol+count,por-1);41         return root;42         43     }44 };