105. Construct Binary Tree from Preorder and Inorder Traversal

题目

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

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

For example, given

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

Return the following binary tree:

	3
   / \
  9  20
    /  \
   15   7

题目大意

根据一棵树的前序遍历与中序遍历构造二叉树。

注意: 你可以假设树中没有重复的元素。

解题思路

• 给出 2 个数组，根据 preorder 和 inorder 数组构造一颗树。
• 利用递归思想，从 preorder 可以得到根节点，从 inorder 中得到左子树和右子树。只剩一个节点的时候即为根节点。不断的递归直到所有的树都生成完成。