思路

通过分治递归的思想，将问题划分到最小，我们创建一个递归方法，传入前序中序数组，以及两个数组>上界与下界 在递归方法内，由于前序数组第一个值必定是根节点这一特性，创建根节点，以根节点为界限，将前序数组与中序数组按左右子树拆分，分别递归的调用方法返回左右子树，直接将节点链接给根节点，再返回根节点即可 注意：

• 中序遍历拆分很简单(vinStart, index - 1)(index + 1,vinEnd)
• 但是前序遍历需要计算我们截取的长度lenth = index - vinStart;
• 即(preStart + 1, preStart + lenth)这里+1是因为前序数组上界索引处的节点必是根节点，我们>- 要向后移一位，然后在上界的基础上加上我们计算的长度
• 后面的截取也就简单(preStart + lenth + 1, preEnd)

代码

import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    /**
     * 重建二叉树
     *
     * @param pre 前序遍历数组
     * @param vin 中序遍历数组
     * @return com.gewuyou.algorithm.problem.TreeNode
     * @apiNote 传入前序遍历数组与中序遍历数组，返回重建后的二叉树的根节点
     * @since 2023/1/7 15:20
     */
    public TreeNode reConstructBinaryTree(int[] pre, int[] vin) {
        if (pre == null || vin == null || pre.length == 0 || vin.length == 0) {
            return null;
        }
        return reConstructBinaryTree(pre, vin, 0, pre.length - 1, 0, vin.length - 1);
    }

    /**
     * 重建二叉树的递归方法
     *
     * @param pre      前序遍历数组
     * @param vin      中序遍历数组
     * @param preStart 前序遍历数组上界
     * @param preEnd   前序遍历数组下界
     * @param vinStart 中序遍历上界
     * @param vinEnd   中序遍历下界
     * @return com.gewuyou.algorithm.problem.TreeNode
     * @apiNote
     * @since 2023/1/7 15:22
     */
    public TreeNode reConstructBinaryTree(int[] pre, int[] vin, int preStart,
                                          int preEnd, int vinStart, int vinEnd) {
        // 如果传入上下界越界则返回空节点
        if (preStart > preEnd || vinStart > vinEnd) {
            return null;
        }
        // 创建根节点 前序遍历首节点为根节点
        TreeNode root = new TreeNode(pre[preStart]);
        // 创建遍历中序数组找到根节点所在位置
        int index = 0;
        while (vin[index] != root.val) {
            index++;
        }
        // 计算截取长度
        int lenth = index - vinStart;
        // 分割前序中序数组，递归调用方法返回左右节点
        root.left = reConstructBinaryTree(pre, vin, preStart + 1, preStart + lenth,
                                          vinStart, index - 1);
        root.right = reConstructBinaryTree(pre, vin, preStart + lenth + 1, preEnd,
                                           index + 1, vinEnd);
        // 返回重建后的二叉树
        return root;
    }

}