刷题日记01：序列化和反序列化二叉树

客官°小女子只卖身不卖艺 2024-03-25 09:30 78阅读 0赞

一.概念理解：

题目如下：[https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/][https_leetcode.cn_problems_xu-lie-hua-er-cha-shu-lcof]

何为序列化？

序列化我们可以理解为层序遍历的结果，即将所有的结点的信息，按照层序遍历的结果拼接到一个字符串中，但是与一般的层序遍历有所不同的是：序列化要输出所有的结点信息，而层序遍历一般不会对null结点进行输出。如下：

![582b4d68e19a57b9de7c4945345fa095.png][]

二.解决思路：

1.序列化:

既然与层序遍历存在相同之处，那么解决思路同样存在相同之处了：

我们解决层序遍历的题目时，一般利用辅助队列空间，即创建一个存放结点的LinkedList,判断当前结点是否非空，不为空则加入到队列中，同时设置一个计数器：不断记录当前队列中存在几个元素，后面输出，力扣题目以及代码如下：

[https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/][https_leetcode.cn_problems_cong-shang-dao-xia-da-yin-er-cha-shu-lcof]

class Solution {
        public int[] levelOrder(TreeNode root) {
            if(root == null) return new int[0];
            Queue<TreeNode> queue = new LinkedList<>(){
        { add(root); }};
            ArrayList<Integer> ans = new ArrayList<>();
            while(!queue.isEmpty()) {
                TreeNode node = queue.poll();
                ans.add(node.val);
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            int[] res = new int[ans.size()];
            for(int i = 0; i < ans.size(); i++)
                res[i] = ans.get(i);
            return res;
        }
    }
    
    作者：jyd
    链接：https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/solution/mian-shi-ti-32-i-cong-shang-dao-xia-da-yin-er-ch-4/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

序列化不需要设置计数器，但是遍历的思路和其完全相同，但是序列化需要利用StringBuilder进行字符串的拼接，就是将每次放入队列的元素拼接到StringBuilder中，null也需要拼接，通过判断队列是否为空，进行不断的循环：

public String serialize(TreeNode root) {
            //检验头结点的合法性
            if(root == null) return "[]";
            //拼接左括号
            StringBuilder res = new StringBuilder("[");
            //将头结点接入
            Queue<TreeNode> queue = new LinkedList<>() {
        { add(root); }};
            while(!queue.isEmpty()) {
                TreeNode node = queue.poll();
                //由于null也需要加入队列，所以这时需判断加入队列的元素是否为null
                if(node != null) {
                    //  将当前结点进行拼接
                    res.append(node.val + ",");
                    //
                    queue.add(node.left);
                    queue.add(node.right);
                }
                //如果是null直接在StringBuilder中拼接null
                else res.append("null,");
            }
            //将最后一个逗号删除
            res.deleteCharAt(res.length() - 1);
            //拼接右半部分括号
            res.append("]");
            return res.toString();

2.反序列化

反序列化可以理解为序列化的逆过程：在序列化字符串中按照下标不断取出新的元素，并判断是否为空，不是空则加入到辅助队列中，不断循环直至队列中的元素为空：循环结束。

具体实现逻辑的代码如下：

public TreeNode deserialize(String data) {
            //如果序列化字符串中的元素为空，直接返回null
            if(data.equals("[]")) return null;
             //转化为字符串数组，便于节点的遍历
            String[] vals = data.substring(1, data.length() - 1).split(",");
            //先将第一个元素加入队列
            TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
            Queue<TreeNode> queue = new LinkedList<>() {
        { add(root); }};
            int i = 1;
            while(!queue.isEmpty()) {
                TreeNode node = queue.poll();
                //以队列是否为空为不断循环的条件
                if(!vals[i].equals("null")) {
                    //当前不为空则加入到队列，并将其作为当前元素的左子节点
                    node.left = new TreeNode(Integer.parseInt(vals[i]));
                    queue.add(node.left);
                }
                i++;
                if(!vals[i].equals("null")) {
                //当前不为空则加入到队列，并将其作为当前元素的右子节点
                    node.right = new TreeNode(Integer.parseInt(vals[i]));
                    queue.add(node.right);
                }
                i++;
            }
            //反序列化结束，返回根节点
            return root;
        }

[https_leetcode.cn_problems_xu-lie-hua-er-cha-shu-lcof]: https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/
[582b4d68e19a57b9de7c4945345fa095.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8e4c906685c24507a48e564b8c88f502.png
[https_leetcode.cn_problems_cong-shang-dao-xia-da-yin-er-cha-shu-lcof]: https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/