剑指 Offer 37. 序列化二叉树

题目

请实现两个函数，分别用来序列化和反序列化二叉树。

你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例：

graph TB
1((1)) --- 2((2))
1 --- 3((3))
3 --- 4((4))
3 --- 5((5))

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

注意：本题与主站297题相同

题解

class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return null;
        }
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>(Collections.singletonList(root));

        // 按照层序序列化
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = size; i > 0; i--) {
                TreeNode node = queue.poll();
                if (node != null) {
                    sb.append(node.val);
                    queue.offer(node.left);
                    queue.offer(node.right);
                } else {
                    sb.append("null");
                }
                sb.append(",");
            }
        }

        sb.deleteCharAt(sb.length() - 1);

        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null) {
            return null;
        }

        int start = 0;
        List<String> nums = Arrays.stream(data.split(",")).collect(Collectors.toList());

        // 初始化根节点
        TreeNode root = new TreeNode(Integer.parseInt(nums.get(start)));
        Queue<TreeNode> queue = new ArrayDeque<>(Collections.singletonList(root));

        // 依次解析左右树
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            String left = nums.get(++start);
            String right = nums.get(++start);
            if (!"null".equals(left)) {
                TreeNode nodeLeft = new TreeNode(Integer.parseInt(left));
                node.left = nodeLeft;
                queue.offer(nodeLeft);
            }

            if (!"null".equals(right)) {
                TreeNode nodeRight = new TreeNode(Integer.parseInt(right));
                node.right = nodeRight;
                queue.offer(nodeRight);
            }
        }

        return root;
    }
}