# Construct Binary Tree from Preorder and Inorder Traversal

## Question

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

Example
Given in-order [1,2,3] and pre-order [2,1,3], return a tree:
2
/ \
1   3
Note
You may assume that duplicates do not exist in the tree.


## 题解

1. preorder 先序遍历的第一个节点即为根节点。
2. 确定 inorder 数组中的根节点后其左子树和右子树也是 preorder 的左子树和右子树。

### Java

/**
* 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 || inorder == null) return null;
if (preorder.length == 0 || inorder.length == 0) return null;
if (preorder.length != inorder.length) return null;

TreeNode root = helper(preorder, 0, preorder.length - 1,
inorder, 0, inorder.length - 1);
return root;
}

private TreeNode helper(int[] preorder, int prestart, int preend,
int[] inorder, int instart, int inend) {
// corner cases
if (prestart > preend || instart > inend) return null;
// build root TreeNode
int root_val = preorder[prestart];
TreeNode root = new TreeNode(root_val);
// find index of root_val in inorder[]
int index = findIndex(inorder, instart, inend, root_val);
// build left subtree
root.left = helper(preorder, prestart + 1, prestart + index - instart,
inorder, instart, index - 1);
// build right subtree
root.right = helper(preorder, prestart + index - instart + 1, preend,
inorder, index + 1, inend);
return root;
}

private int findIndex(int[] nums, int start, int end, int target) {
for (int i = start; i <= end; i++) {
if (nums[i] == target) return i;
}
return -1;
}
}


### 复杂度分析

findIndex 时间复杂度近似 $O(n)$, helper 递归调用，每次调用都需要找中序遍历数组中的根节点，故总的时间复杂度为 $O(n^2)$. 原地生成最终二叉树，空间复杂度为 $O(1)$.