题目描述

解题思路

BFS

https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/solution/mian-shi-ti-37-xu-lie-hua-er-cha-shu-ceng-xu-bian-/
BFS的反序列化也是使用队列来模拟构造树的过程。

public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "[]";
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        StringBuilder res = new StringBuilder().append("[");
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if(node != null) {
                res.append(node.val + ",");
                queue.add(node.left);
                queue.add(node.right);
            }
            else res.append("null,");
        }
        res.deleteCharAt(res.length() - 1);
        res.append("]");
        return res.toString();
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.equals("[]")) return null;
        String[] split = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(split[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (!split[i].equals("null")) {
                node.left = new TreeNode(Integer.parseInt(split[i]));
                queue.offer(node.left);
            }
            // 为null也要+1
            i++;
            if (!split[i].equals("null")) {
                node.right = new TreeNode(Integer.parseInt(split[i]));
                queue.offer(node.right);
            }
            i++;
        }
        return root;
    }
}

DFS

https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/solution/er-cha-shu-de-xu-lie-hua-yu-fan-xu-lie-hua-by-le-2/
DFS序列化就是先序遍历，反序列化就是分割字符串之后进行生成树，注意每次生成了一个节点都需要删除值。

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
    String rserialize = rserialize(root, "");
    return rserialize;
}
public String rserialize(TreeNode root, String str) {
    if (root == null) {
        str += "null,";
        return str;
    }
    str += root.val + ",";
    str = rserialize(root.left, str);
    str = rserialize(root.right, str);
    return str;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    String[] split = data.split(",");
    List<String> list = new ArrayList<String>(Arrays.asList(split));
    return rdeserialize(list);
}
public TreeNode rdeserialize(List<String> dataList) {
    // 递归到null停止，并删除
    if (dataList.get(0).equals("null")) {
        dataList.remove(0);
        return null;
    }
    TreeNode node = new TreeNode(Integer.parseInt(dataList.get(0)));
    // 注意生成节点之后删除元素
    dataList.remove(0);
    node.left = rdeserialize(dataList);
    node.right = rdeserialize(dataList);
    return node;
}