# Construct Binary Tree from Preorder and Inorder Traversal

Datetime:2016-08-23 01:17:02         Topic:         Share        Original >>

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

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

Given in-order [1,2,3] and pre-order [2,1,3], return a tree:

```2
/ \
1   3```
```/**
* Definition of TreeNode:
* public class TreeNode {
*     public int val;
*     public TreeNode left, right;
*     public TreeNode(int val) {
*         this.val = val;
*         this.left = this.right = null;
*     }
* }
*/

public class Solution {
/**
*@param preorder : A list of integers that preorder traversal of a tree
*@param inorder : A list of integers that inorder traversal of a tree
*@return : Root of a tree
*/
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0 || inorder == null ||
inorder.length == 0) {
return null;
}

int preEnd = preorder.length - 1;
int inEnd = inorder.length - 1;

return build(preorder, 0, preEnd, inorder, 0, inEnd);
}

private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return null;
}

int rootVal = preorder[preStart];
int rootIndex = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}

TreeNode root = new TreeNode(rootVal);
root.left = build(preorder, preStart + 1, preStart + rootIndex - inStart, inorder, inStart, rootIndex - 1);
root.right = build(preorder, preStart + rootIndex - inStart + 1, preEnd, inorder, rootIndex + 1, inEnd);

return root;
}
}```

Hope this helps,

Michael