算法思想一:递归
解题思路:
二叉树的前序遍历:根左右;中序遍历:左根右
由前序遍历知道根节点之后,能在中序遍历上划分出左子树和右子树。分别对中序遍历的左右子树递归进行这一过程即可建树。

图解:
图片说明

import java.util.*;

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {

        if (pre.length == 0 || vin.length == 0) {
            return null;
        }

        int root = pre[0];

        if (pre.length == 1) {
            return new TreeNode(root);
        }

        int midIndex = 0;

        //遍历中序数组 找出mid的根节点
        for (int i = 0; i < vin.length; i++) {

            if (vin[i] == root) {
                midIndex = i;
                break;
            }
        }

        TreeNode node = new TreeNode(root);

        node.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, midIndex + 1), Arrays.copyOfRange(vin, 0, midIndex));
        node.right = reConstructBinaryTree(Arrays.copyOfRange(pre, midIndex + 1, pre.length), Arrays.copyOfRange(vin, midIndex + 1, vin.length));

        return node;
    }
}