[数据结构与算法]LeetCode 297. 二叉树的序列化与反序列化

题目链接：

力扣https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/

【分析】序列化的时候很简单，任意的一种二叉树遍历都可以做到，关键是怎么保存树的结构特征，我们可以通过先序遍历的过程中保存null节点来实现。

以样例一为🌰：保存null节点的先序遍历结果为：1,2,null,null,3,4,null,null,5,null,null

在反序列化的过程中，仍然按照先序，

1.取出头节点1，创建为root，剩下的[2,null,null,3,4,null,null,5,null,null]，递归调用构造函数去创建root的left和right。

2.在创建left的过程中，取出头节点2，作为root，剩下的[null,null,3,4,null,null,5,null,null]部分继续调用构造函数，由于头节点为null，直接返回作为root的left，那么root的right部分的构造函数传入的链表就是[null,3,4,null,null,5,null,null]了，头节点同样为null，直接返回作为root的right，这样节点2至此就完全创建好了，值为2，左右节点为null，他返回作为1节点的left。

3.接下来到了创建1节点的right了，剩余的链表中的内容还有[3,4,null,null,5,null,null]，取出头节点3作为right的root节点，然后递归将[4,null,null,5,null,null]继续创建。

总结下来其实这个主要通过对null值的直接返回来保存结构，此外在构建的过程中链表中的节点不断减少。

public class Codec {

    List<Integer> list = new ArrayList();

    public void dfs(TreeNode node){
        if(node == null) list.add(1001);
        else{
            list.add(node.val);
            dfs(node.left);
            dfs(node.right);
        }
    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        dfs(root);
        return list.toString();
    }

    public TreeNode dsrz(Deque<Integer> queue){
        int top = queue.poll();
        if(top == 1001) return null;
        TreeNode root = new TreeNode(top);
        root.left = dsrz(queue);
        root.right = dsrz(queue);
        return root;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] strs = data.substring(1, data.length() - 1).split(",");
        Deque<Integer> queue = new LinkedList();
        for(var str: strs) queue.offer(Integer.parseInt(str.trim()));
        return dsrz(queue);
    }
}

这里有一个小小的作弊的方法，可以不转字符串。改一下函数的返回值

public class Codec {

    Deque<Integer> list = new LinkedList();

    public void dfs(TreeNode node){
        if(node == null) list.offer(1001);
        else{
            list.offer(node.val);
            dfs(node.left);
            dfs(node.right);
        }
    }

    // Encodes a tree to a single string.
    public Deque<Integer> serialize(TreeNode root) {
        dfs(root);
        return list;
    }

    public TreeNode dsrz(Deque<Integer> queue){
        int top = queue.poll();
        if(top == 1001) return null;
        TreeNode root = new TreeNode(top);
        root.left = dsrz(queue);
        root.right = dsrz(queue);
        return root;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(Deque<Integer> queue) {
        return dsrz(queue);
    }
}

?

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖