题解 | #重建二叉树#

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) {
        //创建集合，将数组元素放进去
        List<Integer> listPre = new ArrayList<>();
        List<Integer> listVin = new ArrayList<>();
        for (int i = 0; i < pre.length; i++) {
            listPre.add(pre[i]);
            listVin.add(vin[i]);
        }
        //进行遍历填充
        TreeNode root = order(listPre, listVin);
        return root;
    }
    public TreeNode order(List<Integer> listPre,List<Integer> listVin) {
        //如果为空则返回
        if (listVin.size() == 0) {
            return null;
        }
        //获取根节点值，根节点为pre集合的第一个元素
        int rootVal = listPre.remove(0);
        //初始化跟
        TreeNode root = new TreeNode(rootVal);
        //获取根节点在vin数组中的位置，以便将左右子树以根节点为中心分隔开
        int mid = listVin.indexOf(rootVal);
        //mid的左边就是左子树，
        root.left = order(listPre, listVin.subList(0, mid));
        //mid的右边激素右子树
        root.right=order(listPre,listVin.subList(mid+1,listVin.size()));
        return root;
    }
}