## Algorithm

Problem Nmae: 106. Construct Binary Tree from Inorder and Postorder Traversal

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

Example 1:

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

Example 2:

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

Constraints:

• `1 <= inorder.length <= 3000`
• `postorder.length == inorder.length`
• `-3000 <= inorder[i], postorder[i] <= 3000`
• `inorder` and `postorder` consist of unique values.
• Each value of `postorder` also appears in `inorder`.
• `inorder` is guaranteed to be the inorder traversal of the tree.
• `postorder` is guaranteed to be the postorder traversal of the tree

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct {
int *postorder;
int post_idx;
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->postorder[-- data->post_idx];

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

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

return node;
}

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
data_t data;
data.postorder = postorder;
data.post_idx = postorderSize;
data.inorder = inorder;
return make_tree(&data, 0, inorderSize);
}
``````
Copy The Code &

Input

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

Output

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

### #2 Code Example with Java Programming

```Code - Java Programming```

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

private TreeNode helper(int[] postorder, Map < Integer, Integer> map, int leftIdx, int rightIdx, int[] postIdx) {
if (leftIdx > rightIdx) {
return null;
}
TreeNode root = new TreeNode(postorder[postIdx[0]--]);
int index = map.get(root.val);
root.right = helper(postorder, map, index + 1, rightIdx, postIdx);
root.left = helper(postorder, map, leftIdx, index - 1, postIdx);
return root;
}
}
``````
Copy The Code &

Input

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

Output

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

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const buildTree = function(inorder, postorder) {
const inmap = {};
const posts = postorder;
for (let i = 0; i  <  inorder.length; i++) {
inmap[inorder[i]] = i;
}
return helper(postorder.length - 1, 0, inorder.length - 1);

function helper(postEnd, inStart, inEnd) {
if (postEnd  <  0 || inEnd < inStart) return null;
const val = posts[postEnd];
const idx = inmap["" + val];
const root = new TreeNode(val);
root.left = helper(postEnd - (inEnd - idx) - 1, inStart, idx - 1);
root.right = helper(postEnd - 1, idx + 1, inEnd);

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

Input

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

Output

cmd
[-1]

### #4 Code Example with Python Programming

```Code - Python Programming```

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

Input

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

Output

cmd
[-1]

### #5 Code Example with C# Programming

```Code - C# Programming```

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

private TreeNode BuildTree(int[] inorder, int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd)
{
var root = new TreeNode(postorder[postorderEnd - 1]);

var inorderIndex = inorderStart;
for (; inorderIndex  <  inorderEnd; inorderIndex++)
if (inorder[inorderIndex] == postorder[postorderEnd - 1])
break;

var leftLength = inorderIndex - inorderStart;
if (leftLength > 0)
root.left = BuildTree(inorder, inorderStart, inorderIndex, postorder, postorderStart, postorderStart + leftLength);
if (inorderEnd > inorderIndex + 1)
root.right = BuildTree(inorder, inorderIndex + 1, inorderEnd, postorder, postorderStart + leftLength, postorderEnd - 1);

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

Input

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

Output

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