题解 | #序列化二叉树#

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) {
        // 算法的时间复杂度O(N)，额外空间复杂度O(N)

        // 1.创建StringJoiner，方便格式化拼接序列化字符串
        StringJoiner sj = new StringJoiner(",", "{", "}");

        // 2.调用先序递归函数序列化二叉树
        SerializeProcess(root, sj);
        System.out.println(sj.toString());
        return sj.toString();
    }

    // 先序序列化的递归过程
    public void SerializeProcess(TreeNode root, StringJoiner sj) {
        // 递归出口
        if (root == null) {
            sj.add("#");
            return;
        }
        // 先序 - 先写入当前结点
        sj.add(Integer.toString(root.val));
        // 先序 - 后解决左右子树
        SerializeProcess(root.left, sj);
        SerializeProcess(root.right, sj);
    }

    // 二叉树的先序反序列化
    TreeNode Deserialize(String str) {
        // 1.处理字符串的前缀和后缀，并以,分割
        String prefix = "{";
        String suffix = "}";
        str = str.substring(prefix.length());
        str = str.substring(0, str.length() - suffix.length());
        String[] strs = str.split(",");

        // 2.根据处理后的字符串数组构造队列
        Queue<String> queue = new LinkedList<>();
        for (String s: strs) {
            queue.add(s);
        }

        // 3.调用递归函数反序列化二叉树
        return DeserializeProcess(queue);
    }

    // 先序反序列化的递归过程
    public TreeNode DeserializeProcess(Queue<String> queue) {
        String val = queue.poll();
        if (val == null || "#".equals(val)) {
            // 如果遇到#，表示该结点为空
            return null;
        }
        // 先序 - 新建结点
        TreeNode cur = new TreeNode(Integer.valueOf(val));
        // 先序 - 解决左右子树
        cur.left = DeserializeProcess(queue);
        cur.right = DeserializeProcess(queue);
        // 先序 - 返回本结点
        return cur;
    }
}