题解 | #序列化二叉树#

题意整理

• 序列化：给定一颗二叉树，将二叉树的节点信息转化为字符串存储起来。
• 反序列化：给定一个序列化后的字符串，根据字符串还原出二叉树。

方法一（DFS）

1.解题思路

• 序列化：将大问题拆分为小问题，每次如果还可以递归，就将当前层拆分为当前层的左孩子，加上当前层的右孩子，加上当前层节点值。递归的终止条件是树中没有节点了。
• 反序列化：将序列化后的结果做分割处理，并存放在一个栈里，然后递归地通过栈来重建二叉树，依次确定每次弹出的节点，并记录其左右孩子。

  2.代码实现

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 "#";
        //按左、右、根的顺序序列化（后序遍历）
        return Serialize(root.left)+","+Serialize(root.right)+","+root.val;
  }

    //反序列化
    TreeNode Deserialize(String str) {
       if(str.equals("#")) return null;
       String[] ss=str.split(",");
       Deque<String> stack=new ArrayDeque<>();

       //将序列化后的节点值添加到栈
       for(String s:ss){
           stack.push(s);
       }
       return Deserialize(stack);
  }
    TreeNode Deserialize(Deque<String> stack){
        String val=stack.pop();
        //空节点判断
        if(val.equals("#")) return null;

        //确定当前节点
        TreeNode root=new TreeNode(Integer.valueOf(val));

        //记录当前左子节点和右子节点
        root.right=Deserialize(stack);
        root.left=Deserialize(stack);

        //返回当前节点
        return root;
    }
}

3.复杂度分析

• 时间复杂度：需要遍历二叉树所有的节点，所以时间复杂度为 。
• 空间复杂度：最坏情况下，二叉树退化为链表，递归栈的深度为链表的长度，所以空间复杂度为 。

方法二（BFS）

1.解题思路

• 序列化：如果当前节点为空，则直接加到序列；如果不为空，则先将其值加到序列，再将它的左右孩子入队。
• 反序列化：将序列化后的结果存放在一个字符串数组，如果数组下标位置元素当前不为空，则作为当前节点左孩子或右孩子，将左孩子或右孩子入队。另外左右孩子作为两次判断分别确定，不管是否为空下标i都要后移，表示判断过一次。

动图展示（序列化）：

动图展示（反序列化）：

2.代码实现

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 sb=new StringBuilder();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);

        //层序遍历
        while(!queue.isEmpty()){
            TreeNode node=queue.poll();
            //序列化空节点
            if(node==null){
                sb.append("#,");
            }
            else{
                //序列化当前节点，并将其左右子节点入队
                sb.append(node.val+",");
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        return sb.toString();
  }

    //反序列化
    TreeNode Deserialize(String str) {
       if(str.equals("#")) 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("#")){
                //确定当前节点左孩子，并将其左孩子入队
                node.left=new TreeNode(Integer.valueOf(arr[index]));
                queue.offer(node.left);
            }
            index++;
            if(!arr[index].equals("#")){
                //确定当前节点右孩子，并将其右孩子入队
                node.right=new TreeNode(Integer.valueOf(arr[index]));
                queue.offer(node.right);
            }
            index++;
       }
       return root;
  }

}

3.复杂度分析

• 时间复杂度：需要遍历二叉树所有的节点，所以时间复杂度为 。
• 空间复杂度：需要额外长度为n的队列存储二叉树中所有的节点，所以空间复杂度为 。