题解 | #重建二叉树#

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.Arrays;
public class Solution {
 public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
      if(pre.length==0 ||pre==null)    return null;

       int midIndex= findRootIndex(pre[0],in);

       TreeNode root =new TreeNode(pre[0]);

//        假设 下标    0  1  2  3     4 
//        前序为       1  2  4  5    3
//        中序为       4  5  2  1(m) 3
        //左子树的 Arrays.copyOfRange为左闭右开型  前序 [1,midindex+1) 和中序 [0,midindex) 
        root.left= reConstructBinaryTree(Arrays.copyOfRange(pre,1,midIndex+1),Arrays.copyOfRange(in,0,midIndex));
        //右子树   前序  [midIndex,pre.lenght)  [midIndex+1,in.lenght)
        root.right =reConstructBinaryTree(Arrays.copyOfRange(pre,midIndex+1,pre.length),Arrays.copyOfRange(in,midIndex+1,in.length));
        return root;
    }

    private int  findRootIndex(int pre, int[] in) {

           int index=0;
           while (pre!=in[index]){
               index++;
           }
           return index;
    }
}