LC297—二叉树的序列化与反序列化

Java架构师必看

修改于 2023-09-25 14:56:33

2940

修改于 2023-09-25 14:56:33

文章被收录于专栏：Java架构师必看

难度困难458

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

广度优先遍历

package com.nie.OneJanLC;/* * *@auth wenzhao *@date 2021/1/14 0:09 */

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class LEE297 {
   

    class Codec {
   

        //把树的转化为字符串(使用BFS)
        public String serialize(TreeNode root) {
   
            if (root == null) {
   
                return "#";
            }
            //创建一个队
            Queue<TreeNode> queue = new LinkedList<>();
            StringBuilder res = new StringBuilder();
            //把根节点放入到队列中
            queue.add(root);
            while (!queue.isEmpty()) {
   
                int size = queue.size();
                for (int i = 0; i < size; i++) {
   
                    TreeNode node = queue.poll();
                    if (node == null) {
   
                        res.append("#,");
                        continue;
                    }
                    res.append(node.val + ",");
                    queue.add(node.left);
                    queue.add(node.right);
                }
            }
            return res.toString();
        }

        //把字符串还原为二叉树
        public TreeNode deserialize(String data) {
   
            //如果是"#" ,就表示为一个节点 返回null
            if (data == "#") {
   
                return null;
            }
            //创建一个队
            Queue<TreeNode> queue = new LinkedList<>();
            String[] values = data.split(",");
            //上面使用的是BFS 所以第一个值就是根节点得值,这里创建根节点
            TreeNode root = new TreeNode(Integer.parseInt(values[0]));
            queue.add(root);
            for (int i = 1; i < values.length; i++) {
   

                //队列中移出结点
                TreeNode parent = queue.poll();
                /* 因为在BFS中左右子结点是成对出现得 所以这里挨着的的两个值一个是做左子节点的值 一个是右子节点的值 当前值如果是"#" 就表示这个子节点为空 如果不是就不为空 */
                if (!"#".equals(values[i])) {
   
                    TreeNode left = new TreeNode(Integer.parseInt(values[i]));
                    parent.left = left;
                    queue.add(left);
                }
                if (!"#".equals(values[++i])) {
   
                    TreeNode right = new TreeNode(Integer.parseInt(values[i]));
                    parent.right = right;
                    queue.add(right);
                }
            }
            return root;
        }
    }

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

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

深度优先

package com.nie.OneJanLC;/*
 *
 *@auth  wenzhao
 *@date 2021/1/14  0:09
 */

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class LEE297L {

    class Codec {

        //把树的转化为字符串(使用DFS)
        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<String>(Arrays.asList(data.split("")));
            return  help(queue);
        }

        private TreeNode help(Queue<String> queue) {
            String val = queue.poll();
            if ("#".equals(val)){
                return  null;
            }
            //是否创建当前结点
            TreeNode root = new TreeNode(Integer.valueOf(val));
            root.left=help(queue);
            root.right=help(queue);
            return  root;
        }
    }

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

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