题解 | #序列化二叉树#

方法一（BFS）

1.题意整理

• 实现两个函数，分别用来序列化和反序列化二叉树。
• 序列化是指将二叉树按照某种遍历方式保存为字符串。
• 反序列化是指根据序列化之后的字符串，重建二叉树。

2.思路整理

序列化：按照广度优先遍历的思路，首先将根节点入队，然后每次弹出当前节点，如果为空，说明不存在左右子节点，直接将"null"（用来表示空节点）加入到结果中，并加一个","用来间隔每一个节点。如果不为空，除了将当前节点值加","加入到结果中，还要将左右子节点入队。

图解展示：

反序列化：相当于序列化的逆操作，首先根据","将字符串分割为字符串数组，根据字符串数组第一个元素新建根节点，并将根节点入队。每次弹出当前节点，如果下一个游标处元素不等于"null"，说明不为空，将其作为当前节点左子节点或右子节点，同时将对应子节点入队，如果等于"null"，则同样占用一个位置，需要将游标后移一位。

图解展示：

3.代码实现

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 "null";
        
        //记录序列化之后的节点
        StringBuilder sb=new StringBuilder();
        //新建队列，用于层序遍历
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        
        //层序遍历
        while(!queue.isEmpty()){
            //取出当前节点
            TreeNode node=queue.poll();
            //为空，直接加入到sb，并加一个","
            if(node==null){
                sb.append("null,");
            }
            else{
                //序列化当前节点，并将其左右子节点作为下一层入队
                sb.append(node.val+",");
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        return sb.toString();
  }
    
    TreeNode Deserialize(String str) {
        //如果只有一个"#"，直接返回空树
       if(str.equals("null")) return null;
       //分割为字符串数组
       String[] arr=str.split(",");
       //数组游标
       int index=0;
       //新建队列
       Queue<TreeNode> queue=new LinkedList<>();
       //将第一个元素节点作为根节点
       TreeNode root=new TreeNode(Integer.valueOf(arr[index++]));
       //根节点入队
       queue.offer(root);
       
       while(!queue.isEmpty()){
            TreeNode node=queue.poll();
            //如果游标处节点不为"#"，说明可以作为当前节点的左子节点
            if(!arr[index].equals("null")){
                node.left=new TreeNode(Integer.valueOf(arr[index]));
                //左子节点入队
                queue.offer(node.left);
            }
            index++;
           //如果游标处节点不为"#"，说明可以作为当前节点的右子节点
            if(!arr[index].equals("null")){
                node.right=new TreeNode(Integer.valueOf(arr[index]));
                //右子节点入队
                queue.offer(node.right);
            }
            index++;
       }
       return root;
  }
    
}

4.复杂度分析

• 时间复杂度：序列化需要遍历二叉树所有节点，所以时间复杂度为$O(n)O(n)$，反序列化需要重建所有二叉树的节点，所以时间复杂度也是$O(n)O(n)$。
• 空间复杂度：序列化和反序列化均需要大小不超过n的队列，所以空间复杂度为$O(n)O(n)$。