题解 | #序列化二叉树#

import java.util.*;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    String Serialize(TreeNode root) {
        StringBuilder s = new StringBuilder();
        Queue<TreeNode> seri = new LinkedList<>();
        nodes.add(root);
        while (!seri.isEmpty()) {
            TreeNode node = seri.poll();
            //空节点序列化
            if (node.val == -1) {
                s.append("#");
                continue;
            }
            s.append(Integer.toString(node.val));
            //标记一个节点值结束
            s.append("-");
            //空节点用val = -1的节点来表示
            if (node.left == null) {
                TreeNode dummy = new TreeNode(-1);
                seri.add(dummy);
            } else {
                seri.add(node.right);
            }
            if (node.right == null) {
                TreeNode dummy = new TreeNode(-1);
                seri.add(dummy);
            } else {
                seri.add(node.right);
            }


        }
        return s.toString();
    }
    public Queue<TreeNode> nodes = new LinkedList<>();
    void BFS(TreeNode root) {

        if (nodes.isEmpty()) return;
        if (nodes.peek().val == -1) {
            root.left = null;
            nodes.poll();
        } else {
            root.left = nodes.poll();
            BFS(root.left);
        }
        if (nodes.peek().val == -1) {
            root.right = null;
            nodes.poll();
        } else {
            root.right = nodes.poll();
            BFS(root.right);
        }

    }
    TreeNode Deserialize(String str) {

        char[] c = str.toCharArray();
        int front = -1;
        for (int i = 0; i < c.length; i++) {
            //在front已经有赋值的情况下
            if (front != -1) {
                if (c[i] == '-') {
                    int val = 0;
                    //得到节点值
                    for (int j = front; j < i; j++) {
                        val = val * 10 + (c[j] - '0');
                    }
                    //加入层次节点队列
                    nodes.add(new TreeNode(val));
                    //恢复front
                    front = -1;
                }
                continue;
            }
            if (c[i] == '#') {
                nodes.add( new TreeNode(-1));
                continue;
            }
            if (front == -1) {
                if (c[i] >= '0' && c[i] <= '9') {
                    front = i;
                }
            }
        }

        TreeNode root = nodes.poll();
        BFS(root);




        return root;

    }
}