297. 二叉树的序列化与反序列化

难度: 困难

来源: 每日一题 2023.09.04 拓展

---

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

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

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

示例 1：

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：

输入：root = [1,2]
输出：[1,2]

提示：

• 树中结点数在范围 [0, 104] 内
• -1000 <= Node.val <= 1000

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {

    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {

    }
}

分析与题解

---

• 深度优先遍历

  当碰到这个题目时, 对于如何序列化, 我们只需要进行一次前/中/后序遍历即可. 但是我们需要补全空节点.这也是递归停止判别条件. 这里我们就是使用 "None" 作为空节点.

  这里我们使用了前序遍历, 如果不了解前中后遍历的童鞋, 可以自行去查阅 144. 二叉树的前序遍历, 整体来说比较简单.

  public String rserialize(TreeNode root, String result) {
      if(root == null) {
          result += "None,";
      } else {
          result += result.valueOf(root.val) + ",";
          result = rserialize(root.left, result);
          result = rserialize(root.right, result);
      }
      return result;
  }    
  

  对于反序列化来说, 我们主要是通过 "序列化字符串" → "序列化数组" → "递归构建节点" 这样的一个流程, 当然也是深度优先遍历的原则.

  public TreeNode deserialize(String data) {
      String[] dataStringArray = data.split(",");
      List<String> dataList = new LinkedList<String>(Arrays.asList(dataStringArray));
      return rdeserialize(dataList);
  }
  
  public TreeNode rdeserialize(List<String> dataList) {
      if(dataList.get(0).equals("None")) {
          dataList.remove(0);
          return null;
      }
      TreeNode node = new TreeNode(Integer.valueOf(dataList.get(0)));
      dataList.remove(0);
      node.left = rdeserialize(dataList);
      node.right = rdeserialize(dataList);
      return node;
  }
  

  整体来说, 从序列化到反序列化的过程, 实际上就是两次深度优先遍历, 前中后序都可. 只要保证前后一致即可.

  整体逻辑代码如下所示.

  /**
  * Definition for a binary tree node.
  * public class TreeNode {
  *     int val;
  *     TreeNode left;
  *     TreeNode right;
  *     TreeNode(int x) { val = x; }
  * }
  */
  public class Codec {
  
      // Encodes a tree to a single string.
      public String serialize(TreeNode root) {
          return rserialize(root, "");
      }
  
      // Decodes your encoded data to tree.
      public TreeNode deserialize(String data) {
          String[] dataStringArray = data.split(",");
          List<String> dataList = new LinkedList<String>(Arrays.asList(dataStringArray));
          return rdeserialize(dataList);
      }
  
      public String rserialize(TreeNode root, String result) {
          if(root == null) {
              result += "None,";
          } else {
              result += result.valueOf(root.val) + ",";
              result = rserialize(root.left, result);
              result = rserialize(root.right, result);
          }
          return result;
      }
  
      public TreeNode rdeserialize(List<String> dataList) {
          if(dataList.get(0).equals("None")) {
              dataList.remove(0);
              return null;
          }
          TreeNode node = new TreeNode(Integer.valueOf(dataList.get(0)));
          dataList.remove(0);
          node.left = rdeserialize(dataList);
          node.right = rdeserialize(dataList);
          return node;
      }
  }
  
  // Your Codec object will be instantiated and called as such:
  // Codec ser = new Codec();
  // Codec deser = new Codec();
  // TreeNode ans = deser.deserialize(ser.serialize(root));
  

  复杂度分析:

  • 时间复杂度: O(n), 一次遍历循环, 时间复杂度与二叉树节点数成正相关线性相关.
  • 空间复杂度: O(n), 遍历过程存储节点的数组都是与节点个数成线性关系.

  结果如下所示.