剑指——重建二叉树

 1 /**
 2  * Definition for binary tree
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 import java.util.Arrays;
11 public class Solution {
12     public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
13         //递归基本条件
14         if(pre.length == 0 || in.length == 0)
15             return null;
16         //先确定根节点
17         TreeNode root = new TreeNode(pre[0]);
18         //在中序遍历序列中找到根节点
19         for(int i = 0; i < in.length; i ++){
20             if(in[i] == pre[0]){
21                 root.left = reConstructBinaryTree(
22                     Arrays.copyOfRange(pre, 1, i+1), Arrays.copyOfRange(in, 0, i)
23                 );
24                 root.right = reConstructBinaryTree(
25                     Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1, in.length)
26                 );
27                 break;//加不加好像差不多，不加感觉安全一些，因为我想不清楚
28             }
29         }
30         return root;
31     }
32 }