/*

    前序遍历或者层序遍历都可以，前序遍历要保存二叉树的结构信息

    空节点用符号表示

     */

    StringBuilder s = new StringBuilder();

    // Encodes a tree to a single string.

    public String serialize(TreeNode root) {

        preTra(root);

        return new String(s);

    }

    public void preTra(TreeNode root)

    {

        if (root==null)

        {

            //#代表空节点

            s.append("#");

            s.append(",");

            return;

        }

        s.append(root.val);

        s.append(",");

        preTra(root.left);

        preTra(root.right);

    }

    // Decodes your encoded data to tree.

    public TreeNode deserialize(String data) {

        if (data.length()==0) return null;

        String[] d = data.split(",");

        //用一个链表记录节点，在调用函数中对链表进行改变是会改变堆中真正的链表的

        LinkedList<String> list = new LinkedList<>();

        for (String s :

             d) {

            list.add(s);

        }

        return dehelper(list);

    }

    public TreeNode dehelper(LinkedList<String> list)

    {

        //pollfirst和poll的区别是，前者在为空时会返回null

        String s = list.pollFirst();

        if (s==null||s.equals("#")) return null;

        //按照前序遍历的顺序，依次把节点放回去

        TreeNode cur = new TreeNode(Integer.parseInt(s));

        cur.left = dehelper(list);

        //注意下边这list和上边的list已经不一样了，因为在上边函数中改变了

        // 虽然传入的是list变量的副本，但是原本和副本都是指向一个地址，都会造成改变

        cur.right = dehelper(list);

        return cur;

    }