题解 | #重建二叉树#

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
这个题有三个要注意的点：1.本题的思路是递归重构这个二叉树，要新建一个root，然后找它的left和right，一直递归下去，直到最小的树被构建完成，一层层返回构建整个二叉树。
2.由前序的根定位了中序的根并且分割了左右子树之后，左子树和右子树的长度依旧和前序遍历的左右子树长度一样。简单的说，遍历方式和改变和树的结构无关，这也是确定下标的基本原理。
3.Arrays.copyOfRange方法利用工厂方法创建了数组，但是它的下标是左闭右开的，因此右边界要比下标多一
 */
import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        if(pre.length == 0 || vin.length == 0)return null;
        TreeNode root = new TreeNode(pre[0]);
        for(int i = 0;i < vin.length; i++){
            if(vin[i] == root.val){
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(vin,0,i));
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(vin,i+1,vin.length));
            }
        }
        return root;
    }
}