## Question

>[Leetcode.105 Construct Binary Tree from Preorder and Inorder Traversal
](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/)

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

- Time complexity: O()
- Space complexity: O()

:::

<br>

## Thoughts & Solutions

### YC
:::spoiler Code

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */

var buildTree = function(preorder, inorder) {
    
    // Time: O(n^2), Space: O(n * log(n))
    /**
        3  root:     preorder = [<3>, <9, x, 20,15,7>], inorder = [<x, 9>, 3, <15,20,7>]
        
        // <9, x>,
        9  3-left:   preorder = [9, <x>], inorder = [<x>, 9, < >]
        x  9-left:   preorder = [x], inorder = [<>, x, <>]

        // <20,15,7>
        20 3-right:  preorder = [20, <15,7>], inorder = [<15>, 20, <7>]
        15 20-left:  preorder = [15, <>], inorder = [<15>]
        7  20-right: preorder = [7, <>], inorder = [<7>]
     */

  
    if(!preorder.length) return null;

    const node = new TreeNode(preorder[0]);
    if(!inorder.length) return node;

    const currInorderIdx = inorder.indexOf(node.val); // Time: O(n^2)
    // [start, end)
    const leftInorder = inorder.slice(0, currInorderIdx);
    const rightInorder = inorder.slice(currInorderIdx + 1, inorder.length);
    const leftPreorder = preorder.slice(1, leftInorder.length + 1);
    const rightPreorder = preorder.slice(leftInorder.length + 1, preorder.length)
    node.left = buildTree(leftPreorder, leftInorder);
    node.right = buildTree(rightPreorder, rightInorder);
    return node
};

:::

<hr/>

### Sol
:::spoiler Code

/**
Time Complexity: O(n^2)
Space Complexity: O(n), 
 */

var buildTree = function(preorder, inorder) {
    if(!preorder.length || !inorder.length) return null;
    const root =  new TreeNode(preorder[0])
    const index = inorder.indexOf(preorder[0])
    /*
    Preorder: [3, 9, 1, 20, 15, 7]
    Inorder: [1, 9, 3, 15, 20, 7]
    Preorder[ 9, 1,]  Inorder [1, 9,]
    Preorder[ 1,]     Inorder [1,]
    Preorder[]        Inorder []
    Preorder[ 20, 15, 7,] Inorder [15, 20, 7]
    Preorder[ 15,] Inorder [15]
    ..
    Preorder[ 7,] Inorder [7]
    ..
    */

    root.left = buildTree(preorder.slice(1, index + 1),inorder.slice(0,index))
    root.right = buildTree(preorder.slice(index + 1),inorder.slice(index+1))
    return root
};

:::

<hr/>

### 東


:::spoiler Code

// Time O(n) | Space O(n) - n is the length of preorder/inorder array
var buildTree = function(preorder, inorder) {
    const inorderIdxMap = new Map();
    for(let i = 0; i < inorder.length; i++) {
        inorderIdxMap.set(inorder[i], i);
    }

    function buildTree(preStart, preEnd, inStart, inEnd) {
        if(preStart > preEnd || inStart > inEnd) return null;

        const parentVal = preorder[preStart];
        const parentNode = new TreeNode(parentVal);
        const parentInorderIdx = inorderIdxMap.get(parentVal);
        const leftSubTreeCount = parentInorderIdx - inStart;

        parentNode.left = buildTree(preStart + 1, preStart + leftSubTreeCount, inStart, parentInorderIdx - 1);
        parentNode.right = buildTree(preStart + leftSubTreeCount + 1, preEnd, parentInorderIdx + 1, inEnd);

        return parentNode;
    }

    return buildTree(0, preorder.length - 1, 0, inorder.length - 1);
}

:::

<hr/>

### Jessie

想不出來QQ

看解答啊！

我連暴力解都想不出來 晚點來聽大神解釋T_T

:::spoiler Code

:::

<hr/>

### 皮皮

:::spoiler Code

:::

<hr/>

### Howard

:::spoiler Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree1(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # idea 1
        # time O(N*N)
        # space O(N*N)
        
        if not preorder or not inorder:
            return None
        root_val = preorder[0]
        root = TreeNode(root_val)
        i = inorder.index(root_val)
        
        root.left = self.buildTree(preorder[1:1+i], inorder[:i])
        root.right = self.buildTree(preorder[1+i:], inorder[i+1:])

        return root
    
    def buildTree2(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # idea 2, enhance on idea 1, with less space and time complexity
        # time O(N)
        # space O(N)
        from collections import deque
        idx_map = {inorder[i]: i for i in range(len(inorder))}
        preorder = deque(preorder)
        return self.helper(preorder, 0, len(inorder), idx_map)

    def helper(self, preorder, l, r, idx_map):
        if l >= r:
            return None
        root_val = preorder.popleft()
        root = TreeNode(root_val)
        i = idx_map[root_val]
        
        root.left = self.helper(preorder, l, i, idx_map)
        root.right = self.helper(preorder, i+1, r, idx_map)

        return root

:::

<hr/>

<br>

## Live Coding

:::spoiler (name)

// write your code here

:::