小学生都能看懂的题解 | #序列化二叉树#

序列化：把树变成一串数字和符号

想象一下，我们有一棵圣诞树，上面挂了很多装饰品。我们要记录这棵树的样子，以便以后可以完全复制出来。这里有一个办法：

1. 先看树顶：
1. 我们首先写下树顶（根节点）的装饰品编号。
2. 再看左边的小树枝：
1. 然后看看树顶左边的第一个小树枝（左子树），如果有的话，也记下它的装饰品编号。
2. 如果没有，我们就写一个“#”。
3. 接着看右边的小树枝：
1. 再看看树顶右边的第一个小树枝（右子树），如果有的话，同样记下它的装饰品编号。
2. 如果没有，还是写一个“#”。

然后，对于每个小树枝，我们重复以上三个步骤，直到所有的树枝都被记录下来为止。每次记完一个小树枝的信息后，我们在下一个信息前面加上一个空格。

反序列化：把一串数字和符号变成树

现在我们有了这样一串数字和符号，我们要用它来重建那棵圣诞树：

1. 取出第一个数字：
1. 这个数字代表了树顶（根节点）的装饰品编号。
2. 取出下一个数字或符号：
1. 如果是数字，那么它代表了树顶左边第一个小树枝（左子树）的装饰品编号；
2. 如果是“#”，那就表示左边没有小树枝。
3. 再取出下一个数字或符号：
1. 这次是看树顶右边第一个小树枝（右子树）。
2. 如果是数字，就给右边挂上相应编号的装饰品；如果是“#”，就不挂。

然后，对于每个新挂上的小树枝，我们重复以上三个步骤，直到所有的信息都用完了为止。

下面是简单的代码：

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class Codec {

    // 序列化
    public String serialize(TreeNode root) {
        if (root == null) return "#";
        return root.val + " " + serialize(root.left) + " " + serialize(root.right);
    }

    // 反序列化
    public TreeNode deserialize(String data) {
        Queue<String> queue = new LinkedList<>(Arrays.asList(data.split(" ")));
        return deserializeHelper(queue);
    }

    private TreeNode deserializeHelper(Queue<String> queue) {
        String val = queue.poll();
        if ("#".equals(val)) return null;
        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = deserializeHelper(queue);
        node.right = deserializeHelper(queue);
        return node;
    }
}

如果这篇文章对你有帮助，请点个免费的赞👍，让它能够帮助更多的人。