算法思想一：递归

解题思路：

二叉树的前序遍历：根左右；中序遍历：左根右
由前序遍历知道根节点之后，能在中序遍历上划分出左子树和右子树。分别对中序遍历的左右子树递归进行这一过程即可建树。

图解：

代码展示：

Python版本 
class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if not pre:
            return None
        # 根节点
        root = TreeNode(pre[0])
        # 根节点在中序遍历中的位置索引
        tmp = tin.index(pre[0])
        # 递归 构造树的左子树
        root.left = self.reConstructBinaryTree(pre[1:tmp+1], tin[:tmp])
        # 递归构造树的右子树
        root.right = self.reConstructBinaryTree(pre[tmp+1:], tin[tmp+1:])
        return root

复杂度分析：

时间复杂度O(N)：N表示二叉树的结点数量
空间复杂度O(N)：返回的树占用空间

算法思想二：指针

解题思路：

二叉树的前序遍历：根左右；中序遍历：左根右
设置三个指针，一个是preStart，表示的是前序遍历开始的位置，一个是inStart，表示的是中序遍历开始的位置。一个是inEnd，表示的是中序遍历结束的位置，我们主要是对中序遍历的数组进行拆解
图解：
前序序列：【1，2，3，4，5，6，7】
中序遍历：【3，2，4，1，6，5，7】
只要找到了前序遍历的结点在中序遍历的位置，我们就可以把中序遍历数组分解为左右子树两部分。
1、如果index是前序遍历的某个值在中序遍历数组中的索引，以index为根节点划分，在中序遍历中，[0，index-1]就是根节点左子树的所有节点，[index+1，tin.length-1]就是根节点右子树的所有节点
2、对于前序序列，针对左子树，preStart=index+1，如果是右子树就稍微麻烦点，preStart=preStart+(index-inStart+1)，preStart是当前节点比如m先序遍历开始的位置，index-inStart+1就是当前节点m左子树的数量加上当前节点的数量，所以preStart+(index-instart+1)就是当前节点m右子树前序遍历开始的位置

代码展示：

JAVA版本 
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        return dfs(0, 0, in.length - 1, pre, in);
    }
    
    public TreeNode dfs(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
        if (preStart > preorder.length - 1 || inStart > inEnd) {
            return null;
        }
        //创建结点
        TreeNode root = new TreeNode(preorder[preStart]);
        int index = 0;
        //找到当前节点root在中序遍历中的位置，然后再把数组分两半
        for (int i = inStart; i <= inEnd; i++) { if (inorder[i] == root.val) { index = i; break; } } root.left = dfs(preStart + 1, inStart, index - 1, preorder, inorder); root.right = dfs(preStart + index - inStart + 1, index + 1, inEnd, preorder, inorder); return root; }

复杂度分析：

时间复杂度O(N)：N表示二叉树的结点数量
空间复杂度O(N)：返回的树空间，使用额外指针，常数级空间

算法思想三：栈

解题思路：

二叉树的前序遍历：根左右；中序遍历：左根右
借助栈来解决问题需要关注一个问题，就是前序遍历挨着的两个值比如m和n，它们会有下面两种情况之一的关系。
1、n是m左子树节点的值。
2、n是m右子树节点的值或者是m某个祖先节点的右节点的值。
对于第一种情况很容易理解，如果m的左子树不为空，那么n就是m左子树节点的值。
对于第二种情况，如果一个结点没有左子树只有右子树，那么n就是m右子树节点的值，如果一个结点既没有左子树也没有右子树，那么n就是m某个祖先节点的右节点，只要找到这个祖先节点就可以

代码展示：

JAVA版本 
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre.length == 0)
            return null;
        Stackstack = new Stack<>();
        //前序的第一个其实就是根节点
        TreeNode root = new TreeNode(pre[0]);
        TreeNode cur = root;
        for (int i = 1, j = 0; i < pre.length; i++) { //第一种情况 if (cur.val != in[j]) { cur.left = new TreeNode(pre[i]); stack.push(cur); cur = cur.left; } else { //第二种情况 j++; //找到合适的cur，然后确定他的右节点 while (!stack.empty() && stack.peek().val == in[j]) { cur = stack.pop(); j++; } //给cur添加右节点 cur = cur.right = new TreeNode(pre[i]); } } return root; } }

复杂度分析：

时间复杂度O(N)：N表示二叉树的结点数量
空间复杂度O(1)：额外的栈空间（N个元素），返回树空间