# [LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal ](https://leetcode.com/explore/challenge/card/june-leetcoding-challenge-2021/604/week-2-june-8th-june-14th/3772/)
### Daily challenge Jun 8, 2021 (MEDIAN)

>Given two integer arrays **`preorder`** and **`inorder`** where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.


:::info
**Example 1:**
**Input:** preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
**Output:** [3,9,20,null,null,15,7]
:::

:::info
**Example 2:**
**Input:** preorder = [-1], inorder = [-1]
**Output:** [-1]
:::

:::warning
**Constraints:**
* 1 <= preorder.length <= 3000
* inorder.length == preorder.length
* -3000 <= preorder[i], inorder[i] <= 3000
* preorder and inorder consist of unique values.
* Each value of inorder also appears in preorder.
* preorder is guaranteed to be the preorder traversal of the tree.
* inorder is guaranteed to be the inorder traversal of the tree.
:::

---

### Approach 1 : Recursion :book:
**`16 ms ( 84.60% )`** **`O()`**

:::success
1. Preorder : `root -> left -> right`。
2. Inorder : `left -> root -> right`。
3. Postorder : `left -> right -> root`。
:::

* `preorder` 首個元素即代表 **`root`**。
再去觀察 `inorder`，可以發現 `root` 左邊就是 `Left Subtree`，右邊就是 `Right Subtree`。
* 透過剛剛的觀察，我們可以建立一個 **`Recursion Function`**。
>1. **`left`** ---> `subtree` 的左邊界、**`right`** ---> `subtree` 的右邊界。
>2. **`pre_index`** 表示當前使用的 `root`、
>**`index[]`** 表示元素在 `inorder` 的位置 ( 使用 **`unordered_map`** 紀錄 )。
>3. 先建立當前 `root` 的 `TreeNode `，再建立 `left & right subtree`。
>4. `root` 的 `left subtree` 範圍 ---> **`( left, index[root] - 1)`**。
>`root` 的 `right subtree` 範圍 ---> **`( index[root] + 1, right )`**。
>若 `left > right`，則表示 `root == NULL`。

---

> EXAMPLE : `preorder = [3,9,20,15,7]`, `inorder = [9,3,15,20,7]`。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    map<int, int > index;   // value, index
    int pre_index = 0;
    
    TreeNode* split(vector<int>& preorder, int left, int right){
        if(left > right) return NULL;

        int root_value = preorder[pre_index++];
        TreeNode *root = new TreeNode(root_value);
   
        root->left = split(preorder, left, index[root_value]-1);
        root->right = split(preorder, index[root_value]+1, right);
        
        return root;
    }
    
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i=0; i<inorder.size(); i++){
            index[inorder[i]] = i;
        }
        
        return split(preorder, 0, preorder.size()-1);
    }
};