# 105 - Construct Binary Tree from Preorder and Inorder Traversal

解法一 - Recursion

解題思路如下：

1. 為何我們需要 preorder 跟 inorder？因為 preorder 讓我們知道 root 是哪個 node，而 inorder 讓我們知道哪些屬於 left subtree，哪些屬於 right subtree。

2. 知道哪些屬於左子樹和哪些屬於右子樹後，我們就分別再呼叫兩次 buildTree 把左右子樹分別建好。

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

        // decide root
        TreeNode* root = new TreeNode(preorder[0]);

        // build left & right subtree
        int rootPosInorder = find(inorder.begin(), inorder.end(), preorder[0]) - inorder.begin();

        vector<int> leftPre(&preorder[1], &preorder[1+rootPosInorder]);
        vector<int> leftIn(&inorder[0], &inorder[rootPosInorder]);
        vector<int> rightPre(&preorder[1+rootPosInorder], &preorder[preorder.size()]);
        vector<int> rightIn(&inorder[rootPosInorder+1], &inorder[inorder.size()]);

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

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

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

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

        root->left = buildTree(leftPre, leftIn);
        root->right = buildTree(rightPre, rightIn);

        return root;
    }
};

// idea: use preorder to know root, use inorder to know left and right subtree

不過這麼做的效率並不是很高：

Runtime: 32 ms, faster than 26.24% of C++ online submissions for Construct Binary Tree from Preorder and Inorder Traversal. Memory Usage: 70.2 MB, less than 7.35% of C++ online submissions for Construct Binary Tree from Preorder and Inorder Traversal.