题解 | #重建二叉树#

递归的思想， 例如： 前序序列{1,2,4,7,3,5,6,8} = pre 中序序列{4,7,2,1,5,3,8,6} = in

根据当前前序序列的第一个结点确定根结点，为 1 找到 1 在中序遍历序列中的位置，为 in[3] 切割左右子树，则 in[3] 前面的为左子树， in[3] 后面的为右子树 则切割后的左子树前序序列为：{2,4,7}，切割后的左子树中序序列为：{4,7,2}；切割后的右子树前序序列为：{3,5,6,8}，切割后的右子树中序序列为：{5,3,8,6} 对子树分别使用同样的方法分解

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;
        }
        TreeNode t = new TreeNode(pre[0]);
        for(int i = 0;i<vin.length;i++){
            if(vin[i] == pre[0]){
              //裁剪数组注意做包右不包
                t.left = 
     reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(vin,0,i));
                t.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(vin,i+1,vin.length));
                break;
            }
        }
        return t;
    }
}