/*
1. 开始有点懵住，以为要实现一个简单的fastjson
2. 后看了视频开始一小段，想到生成前序+中序就可以了，或者用堆的模式存一下
3. 看到y总用# 替代 null 来确定整个树之后发现还是这个好。。。。
*/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.

    final static String NULL = "#";
    public String serialize(TreeNode root) {
        List<String> list = new ArrayList<>();
        preOrder(root, list);
        return list.stream().map(String::valueOf).collect(Collectors.joining(","));
    }

    void preOrder(TreeNode root, List<String> buffer){
        if (root == null){
            buffer.add(NULL);
            return;
        }
        buffer.add(String.valueOf(root.val));
        preOrder(root.left, buffer);
        preOrder(root.right, buffer);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        int[] index = new int[1];
        return build(data.split(","), index);
    }

    TreeNode build(String[] data, int[] index){
        if (index[0] >= data.length) return null;
        String val = data[index[0]++];
        if (val.equals(NULL))  return null;
        TreeNode root = new TreeNode(Integer.parseInt(val));
        root.left = build(data, index);
        root.right = build(data, index);
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));