题目

思路

1. 记录其前序遍历和中序遍历和长度 构建二叉树
2. 难点在于构建，应该是需要递归构建，之前自己写出来过，现在好像完全不会写了…
3. 整了半天发现我是忽视了负数和多位数的情况…吐血

代码

    //可以通过遍历保存 首先记录root的长度作为第一个字符 后面记录其中序遍历和前序遍历
    StringBuilder ans = new StringBuilder();
    int length=0;
    public String serialize(TreeNode root) {
        //先记录先序
        pre(root);
        //记录长度
        ans.insert(0,length);
        ans.insert(1," ");

        //中序遍历
        order(root);
        return ans.toString();
    }
    public void pre(TreeNode root){
        if(root==null) return;
        ans.append(root.val+" ");
        length++;
        if(root.left!=null) pre(root.left);
        if(root.right!=null) pre(root.right);
    }
    public void order(TreeNode root){
        if(root==null) return;
        if(root.left!=null) order(root.left);
        ans.append(root.val+" ");
        if(root.right!=null) order(root.right);
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] arr = data.split(" ");
        //获取长度 截取字符串
        int length = Integer.valueOf(arr[0]);
        //截取前序和中序字符串
        int[] pre =new int[length];
        int[] order = new int[length];

        for(int i=0;i<length;i++) pre[i] = Integer.valueOf(arr[1+i]);
        for(int i=0;i<length;i++) order[i] = Integer.valueOf(arr[1+i+length]);

        return Resume(pre,order);
    }
    public TreeNode Resume(int[] pre,int[] order){
        if(order.length==0) return null;
        //根节点
        TreeNode root = new TreeNode(pre[0]);
        //找到根节点在order中的位置 可以找到其左右子树的位置
        int local=0;
        while (order[local] !=root.val) local++;
        //开始截取 由于是数组 所以新建
        int[] left_pre = Arrays.copyOfRange(pre,1,pre.length);
        int[] left_order = Arrays.copyOfRange(order,0,local);
        int[] right_pre = Arrays.copyOfRange(pre,local+1,pre.length);
        int[] right_ord = Arrays.copyOfRange(order,local+1,order.length);


        root.left = Resume(left_pre,left_order);
        root.right = Resume(right_pre,right_ord);
        return root;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59