leetcode-106. 中間シーケンスと後シーケンスからシーケンスを遍歴してツリーを構築する

1435 ワード

詳しくは別のブログを参照してください.
https://blog.csdn.net/u014450222/article/details/80889403
1本の木の中順遍歴と後順遍歴に基づいて二叉樹を構築する.
注意:ツリーに重複する要素がないと仮定できます.
たとえば、
  inorder = [9,3,15,20,7]
  postorder = [9,15,7,20,3]

次のツリーを返します.
    3
   / \
  9  20
    /  \
   15   7
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    int SearchInt(vector inorder,int val)
    {
        for(int i=0;i& inorder, vector& postorder) {
        int n=inorder.size();
        if(n>0)
        {
            TreeNode *root=new TreeNode(postorder[n-1]);// 
            int mid=SearchInt(inorder,root->val);
            vector a,b,c,d;// 
            a.assign(inorder.begin(),inorder.begin()+mid);// :vector assign 
            b.assign(postorder.begin(),postorder.begin()+mid);
            c.assign(inorder.begin()+mid+1,inorder.end());
            d.assign(postorder.begin()+mid,postorder.end()-1);
            root->left=buildTree(a,b);// 
            root->right=buildTree(c,d);// 
            return root;
        }
        else
            return nullptr;
    }
};