# LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

Problem:

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

Solution:

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
int[] preorder, inorder;
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
this.inorder = inorder;
int n = preorder.length;
return buildTree(0, n - 1, 0, n - 1);
}

private TreeNode buildTree(int pre1, int pre2, int in1, int in2) {
if (pre2 < pre1) return null;
if (pre2 == pre1) return new TreeNode(preorder[pre1]);
TreeNode root = new TreeNode(preorder[pre1]);
int pos = 0;
for (int i = in1; i <= in2; i++) {
if (inorder[i] == root.val) {
pos = i;
break;
}
}
root.left = buildTree(pre1 + 1, pre1 + pos - in1, in1, pos - 1);
root.right = buildTree(pre1 + pos - in1 + 1, pre2, pos + 1, in2);
return root;
}
}
```