## Algorithm

Problem Nmae: 105. Construct Binary Tree from Preorder and Inorder Traversal

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.

Example 1:

```Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
```

Example 2:

```Input: preorder = [-1], inorder = [-1]
Output: [-1]
```

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct {
int *preorder;
int pre_idx;
int pre_sz;
int *inorder;
} data_t;

struct TreeNode *make_tree(data_t *data, int start, int end) {
struct TreeNode *node;
int i;

if (start == end) return NULL;

node = malloc(sizeof(struct TreeNode));
//assert(node);
node->val = data->preorder[data->pre_idx ++];

i = start;
while (i  <  end && data->inorder[i] != node->val) i ++;

node->left = make_tree(data, start, i);
node->right = make_tree(data, i + 1, end);

return node;
}

struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
data_t data;

data.preorder = preorder;
data.pre_idx = 0;
data.pre_sz = preorderSize;
data.inorder = inorder;

return make_tree(&data, 0, inorderSize);
}
``````
Copy The Code &

Input

cmd
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output

cmd
[3,9,20,null,null,15,7]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
unordered_map < int, int>m;
for(int i = 0; i  <  inorder.size(); i++) m[inorder[i]] = i;
return helper(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1, m);
}

TreeNode* helper(vector<int>& preorder, int pStart, int pEnd, vector<int>& inorder, int iStart, int iEnd, unordered_map < int, int>& m) {
if(pStart > pEnd) return NULL;
TreeNode* root = new TreeNode(preorder[pStart]);
int i = m[preorder[pStart]];
root->left = helper(preorder, pStart + 1, pStart + i - iStart, inorder, iStart, i - 1, m);
root->right = helper(preorder, pStart + i - iStart + 1, pEnd, inorder, i + 1, iEnd, m);
return root;
}
};
``````
Copy The Code &

Input

cmd
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output

cmd
[3,9,20,null,null,15,7]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
Map map = new HashMap<>();
int[] preorderIndex = {0};
for (int i = 0; i  <  inorder.length; i++) {
map.put(inorder[i], i);
}
return buildTree(preorder, 0, preorder.length - 1, map, preorderIndex);
}

private TreeNode buildTree(int[] preorder, int left, int right, Map < Integer, Integer> map, int[] preorderIndex) {
if (left > right) {
return null;
}
int rootVal = preorder[preorderIndex[0]++];
TreeNode root = new TreeNode(rootVal);
root.left = buildTree(preorder, left, map.get(rootVal) - 1, map, preorderIndex);
root.right = buildTree(preorder, map.get(rootVal) + 1, right, map, preorderIndex);
return root;
}
}
``````
Copy The Code &

Input

cmd
preorder = [-1], inorder = [-1]

Output

cmd
[-1]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const buildTree = function(preorder, inorder) {
if(preorder.length === 0 && inorder.length === 0) return null
const val = preorder[0]
const node = new TreeNode(val)
const inIdx = inorder.indexOf(val)
const leftIn = inorder.slice(0, inIdx)
const rightIn = inorder.slice(inIdx + 1)

const leftPre = preorder.slice(1, leftIn.length + 1)
const rightPre = preorder.slice(leftIn.length + 1)

// console.log(leftIn, rightIn, leftPre, rightPre)
node.left = buildTree(leftPre, leftIn)
node.right = buildTree(rightPre, rightIn)
return node
};
``````
Copy The Code &

Input

cmd
preorder = [-1], inorder = [-1]

Output

cmd
[-1]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution(object):
def buildTree(self, preorder, inorder):
if inorder:
ind = inorder.index(preorder.pop(0))
root = TreeNode(inorder[ind])
root.left = self.buildTree(preorder, inorder[0:ind])
root.right = self.buildTree(preorder, inorder[ind+1:])
return root
``````
Copy The Code &

Input

cmd
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output

cmd
[3,9,20,null,null,15,7]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _105_ConstructBinaryTreeFromPreorderAndInorderTraversal
{
public TreeNode BuildTree(int[] preorder, int[] inorder)
{
if (preorder.Length == 0 || inorder.Length == 0) return null;
return BuildTree(preorder, 0, preorder.Length, inorder, 0, inorder.Length);
}

private TreeNode BuildTree(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd)
{
var root = new TreeNode(preorder[preorderStart]);

var inorderIndex = inorderStart;
for (; inorderIndex  <  inorderEnd; inorderIndex++)
if (inorder[inorderIndex] == preorder[preorderStart])
break;

var leftLength = inorderIndex - inorderStart;
if (leftLength > 0)
root.left = BuildTree(preorder, preorderStart + 1, preorderStart + 1 + leftLength, inorder, inorderStart, inorderIndex);
if (inorderEnd > inorderIndex + 1)
root.right = BuildTree(preorder, preorderStart + 1 + leftLength, preorderEnd, inorder, inorderIndex + 1, inorderEnd);

return root;
}
}
}
``````
Copy The Code &

Input

cmd
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output

cmd
[3,9,20,null,null,15,7]