# 106 - Construct Binary Tree from Inorder and Postorder Traversal

解法一 - Recursion

可以參考 105 的解法一，基本的想法是一樣的，程式碼如下：

/**
 * 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 {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.empty()) return NULL;

        // decide root
        TreeNode* root = new TreeNode(postorder[postorder.size()-1]);

        // build left & right subtree
        int rootPosInorder = find(inorder.begin(), inorder.end(), root->val) - inorder.begin();
        cout << rootPosInorder << endl;

        vector<int> leftIn(&inorder[0], &inorder[rootPosInorder]);
        vector<int> leftPost(&postorder[0], &postorder[leftIn.size()]);
        vector<int> rightIn(&inorder[rootPosInorder+1], &inorder[inorder.size()]);
        vector<int> rightPost(&postorder[leftIn.size()], &postorder[postorder.size()-1]);

        /*
        for(int i=0; i<leftIn.size(); i++)
            cout << leftIn[i] << " ";
        cout << endl;

        for(int i=0; i<leftPost.size(); i++)
            cout << leftPost[i] << " ";
        cout << endl;

        for(int i=0; i<rightIn.size(); i++)
            cout << rightIn[i] << " ";
        cout << endl;

        for(int i=0; i<rightPost.size(); i++)
            cout << rightPost[i] << " ";
        cout << endl;
        */

        root->left = buildTree(leftIn, leftPost);
        root->right = buildTree(rightIn, rightPost);

        return root;
    }
};

效率也還不夠好就是了：

Runtime: 24 ms, faster than 63.61% of C++ online submissions for Construct Binary Tree from Inorder and Postorder Traversal. Memory Usage: 70.2 MB, less than 7.76% of C++ online submissions for Construct Binary Tree from Inorder and Postorder Traversal.