题解 | #序列化二叉树#

借助层序遍历

序列化的过程，就是层序遍历逐步拼接字符串的过程

1. 遇到空节点不要跳过，逆序列化的时候要告诉调用方，哪个节点是空的

逆序列化是反向思维，通过数组创建一棵树。很多人到这里就没有思路了，不知道咋创建树，其实仍然逃不脱遍历的策略。

1. 借助队列 queue，从根节点开始逐步展开，遇到空节点要跳过，也要压入 queue 中
2. 节点的 val 来自于序列号数组 str[]，数组的取值自然通过 index 这个指数指针逐步读取
3. 值得注意的是，左右子节点都要移动 index, 空节点也不例外。

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 {
    int index = -1;

    String Serialize(TreeNode root) {
        StringBuilder builder = new StringBuilder();
        if (root == null) {
            return builder.append("{}").toString();
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root); // 层序遍历
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            // node == null ? builder.append('#') : builder.append(node.val);
            if (node == null) {
                builder.append('#').append(",");
            } else {
                builder.append(node.val).append(",");
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        // 移除最后一个逗号
        builder.setLength(builder.length() - 1);
        return "{" + builder.toString() + "}";
    }

    TreeNode Deserialize(String data) {
        if (data.equals("{}")) return null;
        // 去掉开头和结尾的花括号并按逗号分割
        String[] nodes = data.substring(1,data.length()-1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int index = 1;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            // 构造左节点
            if(!nodes[index].equals("#")){
                node.left = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(node.left);
            }

            index++;

            // 构造右节点
            if(!nodes[index].equals("#")){
                node.right = new TreeNode(Integer.parseInt(nodes[index]));
                queue.offer(node.right);
            }

            index++;
        }

        return root;
    }
}