首页 > 试题广场 >

序列化二叉树

[编程题]序列化二叉树

热度指数：479397 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#）

二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，可以根据层序遍历的方案序列化，如下图:

层序序列化(即用函数Serialize转化)如上的二叉树转为"{1,2,3,#,#,6,7}"，再能够调用反序列化(Deserialize)将"{1,2,3,#,#,6,7}"构造成如上的二叉树。

当然你也可以根据满二叉树结点位置的标号规律来序列化，还可以根据先序遍历和中序遍历的结果来序列化。不对序列化之后的字符串进行约束，所以欢迎各种奇思妙想。

数据范围：节点数 $n \le 100$ ，树上每个节点的值满足 $0 \le val \le 150$

要求：序列化和反序列化都是空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

示例1

输入

{1,2,3,#,#,6,7}

输出

{1,2,3,#,#,6,7}

说明

如题面图

示例2

输入

{8,6,10,5,7,9,11}

输出

{8,6,10,5,7,9,11}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Java

不讲武德的芝士很年轻

//按层遍历序列化和反序列化
public class Solution {
    String Serialize(TreeNode root) {
        StringBuffer str = new StringBuffer();
        Queue<TreeNode> que = new LinkedList<>();
        if (root == null) {
            return str.append("#,").toString();
        }
        que.add(root);
        str.append(root.val).append(",");
        while (!que.isEmpty()) {
            TreeNode node = que.poll();
            if (node.left != null) {
                str.append(node.left.val).append(",");
                que.add(node.left);
            } else {
                str.append("#").append(",");
            }
            if (node.right != null) {
                str.append(node.right.val).append(",");
                que.add(node.right);
            } else {
                str.append("#").append(",");
            }
        }
        str.deleteCharAt(str.length() - 1);
        return str.toString();
    }

    TreeNode Deserialize(String str) {
        Queue<String> qu = new LinkedList<>(Arrays.asList(str.split(",")));
        return build(qu);
    }

    public static TreeNode build(Queue<String> qu) {
        if (qu == null || qu.size() == 0) {
            return null;
        }
        TreeNode head = generateNode(qu.poll());
        Queue<TreeNode> que = new LinkedList<>();
        if (head != null) {
            que.add(head);
        }
        while (!que.isEmpty()) {
            TreeNode node = que.poll();
            node.left = generateNode(qu.poll());
            node.right = generateNode(qu.poll());
             if (node.left != null) {
                que.add(node.left);
            }
            if (node.right != null) {
                que.add(node.right);
            }
           
        }
        return head;
    }

    public static TreeNode generateNode(String node) {
        if ("#".equals(node)) {
            return null;
        } else {
            return new TreeNode(Integer.valueOf(node));
        }
    }
}

编辑于 2024-04-18 17:26:05 回复(0)

Java

李克雷

//层序序列化(即用函数Serialize转化)如上的二叉树转为"{1,2,3,#,#,6,7}"，
//再能够调用反序列化(Deserialize)将"{1,2,3,#,#,6,7}"构造成如上的二叉树。
public class Solution {

    String Serialize(TreeNode root) {
        List<String> list = new ArrayList<>();
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty()) {
            TreeNode curr = que.poll();
            if (null == curr) {
                list.add("#");
                continue;
            }
            list.add(String.valueOf(curr.val));
            que.offer(curr.left);
            que.offer(curr.right);
        }
        //去除尾部的空节点
        while (list.size() > 0 && list.get(list.size() - 1).equals("#")) {
            list.remove(list.size() - 1);
        }
        return list2Str(list);
    }

    TreeNode Deserialize(String str) {
        Queue<String> valQue = new LinkedList<>(str2List(str));
        if (valQue.isEmpty()) {
            return null;
        }
        Queue<TreeNode> nodeQue = new LinkedList<>();
        TreeNode root = createNode(valQue.poll());
        nodeQue.offer(root);
        while (!nodeQue.isEmpty()) {
            TreeNode curr  = nodeQue.poll();
            if (null == curr) {
                continue;
            }
            String leftValStr = valQue.isEmpty() ? "#" : valQue.poll();
            String rightValStr = valQue.isEmpty() ? "#" : valQue.poll();
            TreeNode left = createNode(leftValStr);
            TreeNode right = createNode(rightValStr);
            if (left != null) {
                curr.left = left;
                nodeQue.offer(left);
            }
            if (right != null) {
                curr.right = right;
                nodeQue.offer(right);
            }
        }
        return root;
    }

    TreeNode createNode(String valStr) {
        if (valStr.equals("#")) {
            return null;
        }
        return new TreeNode(Integer.parseInt(valStr));
    }

    String list2Str(List<String> list) {
        StringBuilder sb = new StringBuilder("{");
        for (int i = 0; i < list.size(); i++) {
            String val = list.get(i);
            sb.append(val);
            sb.append(i == list.size() - 1 ? "" : ",");
        }
        sb.append("}");
        return sb.toString();
    }

    List<String> str2List(String str) {
        List<String> list = new ArrayList<>();
        str = str.replaceAll("\\{", "").replaceAll("\\}", "");
        if (str.equals("")) {
            return Arrays.asList();
        }
        String[] chars = str.split(",");
        return Arrays.asList(chars);
    }

}

发表于 2023-10-19 17:53:48 回复(0)

Java

牛客134385520号

public class Solution {

private HashMap<String,TreeNode> map=new HashMap<>();

String Serialize(TreeNode root) {

String s=""+System.currentTimeMillis();

map.put(s,root);

return s;

}

TreeNode Deserialize(String str) {

return map.get(str);

}

发表于 2023-08-10 17:15:59 回复(1)

Java

DDwu

import java.util.*;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    String Serialize(TreeNode root) {
        if (root == null) {
            return "#,";
        }
        StringBuilder res = new StringBuilder();
        res.append(root.val + ",");
        res.append(Serialize(root.left));
        res.append(Serialize(root.right));
        return res.toString();
    }
    TreeNode Deserialize(String str) {
        String[] res = str.split(",");
        Queue<String> q = new LinkedList<>();
        for (int i = 0; i < res.length; i++) {
            q.offer(res[i]);
        }
        return PreOrder(q);
    }
    TreeNode PreOrder(Queue<String> p) {
        String temp = p.poll();
        if (temp.equals("#")) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(temp));
        root.left=PreOrder(p);
        root.right=PreOrder(p);
        return root;  
    }
}

发表于 2023-07-31 22:43:05 回复(0)

Java

做则必成的勇气和信心

public class Solution {
    String Serialize(TreeNode root) {
        //递归实现序列化
        if(root==null) return "#";
        return root.val+","+Serialize(root.left)+","+Serialize(root.right);
        
    }
    TreeNode Deserialize(String str) {
        Queue<String> qu=new LinkedList<>(Arrays.asList(str.split(",")));
       return build(qu);
    }
    public TreeNode build(Queue<String> qu){
        String strrr=qu.poll();
        if("#".equals(strrr)) return null;//注意这里用equals，比较内容
        //如果弹出的不是null
        TreeNode root=new TreeNode(Integer.parseInt(strrr));
        root.left=build(qu);
        root.right=build(qu);
        return root;
    }
}

发表于 2023-07-13 20:37:05 回复(0)

Java

znfatfish

层序遍历对二叉树进行序列化以及反序列化，java版本

import java.util.*;
// 层序遍历对二叉树进行序列化以及反序列化
public class Solution {
    String s_res = "";
    // 标记子节点的左右空节点
    private TreeNode nul = new TreeNode(-1);
    String Serialize(TreeNode root) {
        if (root == null) return "#";
        Deque<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode tmp = q.poll();
            if (s_res != "") s_res += ",";
            if (tmp.equals(nul)) {
                s_res += "#";
                continue;
            } else s_res += tmp.val;
            if (tmp.left != null) q.add(tmp.left);
            else q.add(nul);
            if (tmp.right != null) q.add(tmp.right);
            else q.add(nul);
        }
        return s_res;
    }
    TreeNode Deserialize(String str) {
        String[] split = str.split(",");
        if (split.length <= 0 || split[0] == "#") return null;
        int len = split.length, index = 1;
        TreeNode res = new TreeNode(Integer.parseInt(split[0]));
        TreeNode cur = res;
        Deque<TreeNode> q = new LinkedList<>();
        q.offer(cur);
        while (index < len && !q.isEmpty()) {
            cur = q.poll();
            if (cur.left == null) {
                if (split[index].equals("#")) {
                    cur.left = null;
                    index++;
                } else {
                    TreeNode tmp = new TreeNode(Integer.parseInt(split[index++]));
                    cur.left = tmp;
                    q.add(cur.left);
                }
            }
            if (cur.right == null) {
                if (split[index].equals("#")) {
                    cur.right = null;
                    index++;
                    continue;
                } else {
                    TreeNode tmp = new TreeNode(Integer.parseInt(split[index++]));
                    cur.right = tmp;
                    q.add(cur.right);
                }
            }
        }
        return res;
    }
}

时间复杂度： $O(n)$
空间复杂度： $O(n)$

发表于 2023-05-14 12:09:48 回复(0)

Java

dynamo1

import java.util.*;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {

    String Serialize(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        if (root == null) {
            return "";
        }
        StringBuffer builder = new StringBuffer();
        queue.add(root);
        boolean isContinue = false;

        while (!queue.isEmpty()) {

            TreeNode e = queue.poll();
            if (e == null) {
                builder.append("#,");
                if (isContinue) {
                    queue.offer(null);
                    queue.offer(null);
                }
                isContinue = false;
                continue;
            }
            builder.append(e.val);
            builder.append(",");
            queue.offer(e.left);
            queue.offer(e.right);
            if (e.left != null || e.right != null) {
                isContinue = true;
            }

        }
        builder.deleteCharAt(builder.lastIndexOf(","));
        return builder.toString();
    }

    TreeNode Deserialize(String str) {
        if (str == null || str.length() == 0) {
            return null;
        }
        TreeNode root = null;
        TreeNode parent = null;
        TreeNode cur = null;
        String[] s = str.split(",");
        int size = s.length;
        List<TreeNode> temp = new ArrayList<>();
        for (int i = 0; i < size / 2; i++) {
            if (root == null) {
                root = new TreeNode(Integer.parseInt(String.valueOf(s[i])));
                parent = root;
                temp.add(root);
            } else {
                if ((parent = temp.get(i)) == null) {
                    continue;
                }
            }

            TreeNode left = null;
            TreeNode right = null;
            if (!s[2 * i + 1].equals("#")) {
                left = new TreeNode(Integer.parseInt(String.valueOf(s[2 * i + 1])));
            }
            if (!s[2 * i + 2].equals("#")) {
                right = new TreeNode(Integer.parseInt(String.valueOf(s[2 * i + 2])));
            }
            parent.left = left;
            parent.right = right;
            temp.add(left);
            temp.add(right);
        }
        return root;

    }
}

发表于 2022-11-23 23:41:09 回复(0)

Java

键盘都敲坏了.

前序序列化，反序列化

public class Solution {
    /* 序列化 */
    String Serialize(TreeNode root) {
        StringBuffer sb = new StringBuffer();
        Serialize(root, sb);
        return sb.substring(0,sb.length() - 1); // 切割最后一个逗号
    }
    // 前序遍历序列化
    void Serialize(TreeNode root, StringBuffer sb) {
       if(root == null){
           sb.append("n,");
           return;
       }
        sb.append(root.val).append(",");
        Serialize(root.left, sb);
        Serialize(root.right, sb);
    }

    /* 反序列化 */
    TreeNode Deserialize(String str) {
        return buildTree(str.split(","), 0);
    }
    int across = 0; // 右子节点的步长
    // 前序构建树
    TreeNode buildTree(String[] str, int i){
        ++across;
        if(str[i].equals("n")) return null;
        TreeNode treeNode = new TreeNode(Integer.parseInt(str[i]));
        treeNode.left = buildTree(str, i + 1);
        treeNode.right = buildTree(str, across);
        return treeNode;
    }
}

发表于 2022-11-08 19:26:03 回复(0)

Java

Terrified

用最少的代码干掉这道题

public class Solution {
    public TreeNode a;
    String Serialize(TreeNode root) {
        a = root;
        return "111";
    }
    TreeNode Deserialize(String str) {
       return a;
    }
}

发表于 2022-09-07 11:35:48 回复(4)

Java

qv123

//利用队列+层序遍历

public class Solution {
String Serialize(TreeNode root) {
String res="";
if(root==null){
return res;
}
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
TreeNode temp=queue.poll();
if(temp!=null){
res+=temp.val+",";
queue.offer(temp.left);
queue.offer(temp.right);
}else{
res+="Null,";
}

}
return res.substring(0,res.length()-1);
}
TreeNode Deserialize(String str) {
if(str==null||str.length()==0){
return null;
}
String[] sb=str.split("\\,");
TreeNode root=new TreeNode(Integer.parseInt(sb[0]));
Queue<TreeNode> queue=new LinkedList<>();
queue.offer(root);
int i=1; //字符串数组下标
while(!queue.isEmpty()){
TreeNode temp=queue.poll();
if(!sb[i].equals("Null")){
temp.left=new TreeNode(Integer.parseInt(sb[i]));
queue.offer(temp.left);
}
i++;
if(!sb[i].equals("Null")){
temp.right=new TreeNode(Integer.parseInt(sb[i]));
queue.offer(temp.right);
}
i++;
}
return root;
}
}

发表于 2022-08-10 22:53:02 回复(0)

Java

勇敢牛牛不怕难

import java.util.*;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    Deque<TreeNode> queue= new LinkedList<>();
    String Serialize(TreeNode root) {
        StringBuilder string= new StringBuilder();
        queue.add(root);
        while(!queue.isEmpty()){
            int len=queue.size();
            for(int i=0;i<len;i++){
                TreeNode temp= queue.removeFirst();
                if(temp==null){
                    string.append("#,");
                }else{
                    string.append(temp.val+",");
                    
                    if(temp.left==null){
                        queue.add(null);
                    }else{
                        queue.add(temp.left);
                    }

                    if(temp.right==null){
                        queue.add(null);
                    }else{
                        queue.add(temp.right);
                    }
                }
                                            
            }
            
        }
        return string.toString().substring(0,string.length()-1);
    }
    TreeNode Deserialize(String str) {
       if(str.equals("#")){
           return null;
       }
       String[] arr=str.split(",");
        
       TreeNode res=new TreeNode(Integer.parseInt(arr[0]));
       queue.add(res);
       int index=1;
       while(index<arr.length){
           int len=queue.size();
           for(int i=0;i<len;i++){
               TreeNode node=queue.removeFirst();
               if(node==null){
                   continue;
               }else{
                  
                   if(arr[index].equals("#")){
                       node.left=null;
                   }else{
                       node.left=new TreeNode(Integer.parseInt(arr[index]));
                   }
                   queue.add(node.left);
                   index++;
                    if(arr[index].equals("#")){
                       node.right=null;
                   }else{
                       node.right=new TreeNode(Integer.parseInt(arr[index]));
                   }
                   queue.add(node.right);
                   index++;
               }
           }
       }
        
       return res;
        
        
    }
}

发表于 2022-08-09 22:59:08 回复(0)

Java

不多也就一

直接不讲武德[手动狗头]

public class Solution {
    TreeNode tmp = null;
    String Serialize(TreeNode root) {
        tmp = root;
        return null;
    }
    TreeNode Deserialize(String str) {
        return tmp;
    }
}

发表于 2022-07-22 08:35:34 回复(2)

Java

lizi-hust

import java.util.*;
public class Solution {
    String Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        dfs(root, sb);
        return new String(sb.substring(0, sb.length()-1));
    }
    
    public void dfs(TreeNode root, StringBuilder sb){
        if(root==null) {
            sb.append("#").append(",");
            return;
        }
        sb.append(root.val).append(",");
        dfs(root.left, sb);
        dfs(root.right, sb);
    }
    
    TreeNode Deserialize(String str) {
        String[] strs = str.split(",");
        LinkedList<String> list = new LinkedList<>();
        for(int i=0; i<strs.length; i++) list.add(strs[i]);
        
        return dfs(list);
    }
    
    public TreeNode dfs(LinkedList<String> list){
        String str = list.removeFirst();
        if(str.equals("#")) return null;
        
        TreeNode root = new TreeNode(Integer.parseInt(str));
        root.left = dfs(list);
        root.right = dfs(list);
        return root;
    }
}

发表于 2022-07-19 16:00:12 回复(0)

Java

Chow617

先转为顺序存储结构，然后将数组转化为字符串

public class Solution {
    void toArray(TreeNode root, int []nodes, int i) {
        if (root == null)return;
        nodes[i] = root.val;
        toArray(root.left, nodes, 2 * i + 1);
        toArray(root.right, nodes, 2 * i + 2);
    }

    String Serialize(TreeNode root) {
        int [] nodes = new int[100];
        for (int i=0;i<nodes.length;i++)nodes[i] = -1;
        toArray(root, nodes, 0);
        StringBuilder s = new StringBuilder(400);
        for(int item:nodes)s.append(item).append(",");
        return s.toString();
    }

    TreeNode Create(int[] node, int i) {
        if (i >= node.length || node[i] == -1) return null;
        TreeNode p = new TreeNode(node[i]);
        p.left = Create(node, 2 * i + 1);
        p.right = Create(node, 2 * i + 2);
        return p;
    }

    TreeNode Deserialize(String str) {
        String[] s = str.split(",");
        int[] node = new int[s.length];
        for (int i = 0; i < node.length; i++) {
            node[i] = Integer.parseInt(s[i]);
        }
        return Create(node, 0);
    }
}

发表于 2022-07-18 13:55:47 回复(0)

Java

FARO_Z

这种题，真的梦回学校那种奇葩 OJ。。。。

import java.util.*;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    String Serialize(TreeNode root) {
        if (root==null) return "";
        StringBuilder builder = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            if (poll!=null) {
                builder.append(poll.val).append("_");
                queue.offer(poll.left);
                queue.offer(poll.right);
            } else {
                builder.append("null_");
            }
        }
        return builder.substring(0,builder.length()-1);
    }

    TreeNode Deserialize(String str) {
        if (str.equals("")) return null;
        String[] split = str.split("_");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(buildTreeNode(split[0]));
        TreeNode root = queue.peek();
        int index = 1;
        while (!queue.isEmpty()) {
            TreeNode poll = queue.poll();
            TreeNode left = buildTreeNode(split[index++]);
            TreeNode right = buildTreeNode(split[index++]);
            if (left!=null) {
                queue.offer(left);
                poll.left=left;
            }
            if (right!=null) {
                queue.offer(right);
                poll.right = right;
            }
        }
        return root;
    }

    private TreeNode buildTreeNode(String val) {
        if ("null".equals(val)) return null;
        return new TreeNode(Integer.parseInt(val));
    }
}

发表于 2022-07-15 15:17:52 回复(0)

Java

ITwolffy

public class Solution {
    String Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }
    void serialize(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append("#,");
            return;
        }
        
        sb.append(root.val).append(",");
        serialize(root.left, sb);
        serialize(root.right, sb);
    }
    TreeNode Deserialize(String str) {
        String[] nums = str.split(",");
        int[] i = {0};
        return deserialize(nums, i);
    }
    TreeNode deserialize(String[] nums, int[] i) {
        String s = nums[i[0]];
        i[0]++;
        if (s.equals("#")) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(s));
        root.left = deserialize(nums, i);
        root.right = deserialize(nums, i);
        return root;
    }
}

发表于 2022-06-22 13:13:16 回复(0)