LeetCode297 二叉树的序列化与反序列化

LeetCode297 二叉树的序列化与反序列化

1. 思路分析

   1. 前序遍历方式

      1. 将二叉树使用前序遍历打平到一个字符串中，使用SEP = ","表示分隔符，NULL = "#"表示空指针

      2. 将字符串根据SEP分割成nodes。一般来说，单单前序遍历结果是不能还原二叉树结构的，因为缺少空指针的信息，至少要得到前、中、后序遍历中的两种才能还原二叉树。但是这里的nodes列表包含空指针（#）的信息，因此使用nodes列表就可以还原二叉树

         过程也是前序遍历

   2. 后序遍历方式

      1. 将二叉树使用后序遍历打平到一个字符串中，使用SEP = ","表示分隔符，NULL = "#"表示空指针

      2. 反序列化过程与前序遍历方式不同：根节点不再在第一个元素，而是在最后一个元素，因此要从后往前遍历列表进行还原二叉树结构，又因为列表结构如下，所以要先构建右子树，再构建左子树

      3. 示意图

   3. 中序遍历方式 行不通：因为我们找不到root节点

   4. 层序遍历方式

      1. 将二叉树使用层序遍历打平到一个字符串中，使用SEP = ","表示分隔符，NULL = "#"表示空指针

      2. 反序列化过程仍然使用层序遍历，是层序遍历框架的变形，标准的层序遍历在 *** 作二叉树节点TreeNode，而我们在 *** 作nodes[i]

      3. 示意图

2. 代码实现

   1. 前序遍历方式

      public class Codec {
          //separation 分开的
          String SEP = ",";
          String NULL = "#";
          // Encodes a tree to a single string.
          //主函数，将以root 为根节点的二叉树序列化
          public String serialize(TreeNode root) {
              StringBuilder sb = new StringBuilder();
              serialize(root, sb);
              return sb.toString();
          }
          //辅助函数，将二叉树存入StringBuilder
          void serialize(TreeNode root, StringBuilder sb) {
              if (root == null) {
                  sb.append(NULL).append(SEP);
                  return;
              }
              //前序遍历位置
              sb.append(root.val).append(SEP);
      
              serialize(root.left, sb);
              serialize(root.right, sb);
          }
          // Decodes your encoded data to tree.
          //主函数，将二叉树反序列化为二叉树结构
          public TreeNode deserialize(String data) {
              LinkedList nodes = new LinkedList<>();
              for (String node : data.split(SEP)) {
                  nodes.addLast(node);
              }
              return deserialize(nodes);
          }
          //辅助函数，通过nodes列表构造二叉树
          TreeNode deserialize(LinkedList nodes) {
              if (nodes.isEmpty()) {
                  return null;
              }
              //前序遍历位置
              //删除并返回第一个元素
              String node = nodes.removeFirst();
              //如果是空指针
              if (node.equals(NULL)) {
                  return null;
              }
              TreeNode root = new TreeNode(Integer.parseInt(node));
      
              root.left = deserialize(nodes);
              root.right = deserialize(nodes);
              return root;
          }
      }
      

   2. 后序遍历

      public class Codec {
          //separation 分开的
          String SEP = ",";
          String NULL = "#";
          // Encodes a tree to a single string.
          //主函数，将以root 为根节点的二叉树序列化
          public String serialize(TreeNode root) {
              StringBuilder sb = new StringBuilder();
              serialize(root, sb);
              return sb.toString();
          }
          //辅助函数，将二叉树存入StringBuilder
          void serialize(TreeNode root, StringBuilder sb) {
              if (root == null) {
                  sb.append(NULL).append(SEP);
                  return;
              }
      
              serialize(root.left, sb);
              serialize(root.right, sb);
      
              //后序遍历位置
              sb.append(root.val).append(SEP);
          }
          // Decodes your encoded data to tree.
          //主函数，将二叉树反序列化为二叉树结构
          public TreeNode deserialize(String data) {
              LinkedList nodes = new LinkedList<>();
              for (String node : data.split(SEP)) {
                  nodes.addLast(node);
              }
              return deserialize(nodes);
          }
          //辅助函数，通过nodes列表构造二叉树
          TreeNode deserialize(LinkedList nodes) {
              if (nodes.isEmpty()) {
                  return null;
              }
              //从后往前遍历，因为根节点在最后
              String node = nodes.removeLast();
              //如果是空指针
              if (node.equals(NULL)) {
                  return null;
              }
              TreeNode root = new TreeNode(Integer.parseInt(node));
      
              //一定要先构建右子树，在构建左子树
              root.right = deserialize(nodes);
              root.left = deserialize(nodes);
              return root;
          }
      }
      

   3. 层序遍历

      public class Codec {
          String SEP = ",";
          String NULL = "#";
          // Encodes a tree to a single string.
          //使用层序遍历将二叉树序列化
          public String serialize(TreeNode root) {
              if (root == null) {
                  return null;
              }
              //存放二叉树序列化结果
              StringBuilder sb = new StringBuilder();
              Queue q = new LinkedList<>();
              q.offer(root);
      
              while (!q.isEmpty()) {
                  TreeNode cur = q.poll();
                  //如果为空，则加入#，没有左右子节点就要continue
                  if (cur == null) {
                      sb.append(NULL).append(SEP);
                      continue;
                  }
                  sb.append(cur.val).append(SEP);
                  q.offer(cur.left);
                  q.offer(cur.right);
              }
              return sb.toString();
          }
      
          // Decodes your encoded data to tree.
          //使用层序遍历将二叉树反序列化
          public TreeNode deserialize(String data) {
              if (data == null) {
                  return null;
              }
              String[] nodes = data.split(SEP);
              //root节点为第一个
              TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
              Queue q = new LinkedList<>();
              q.offer(root);
      
              for (int i = 1; i < nodes.length;) {
                  TreeNode parent = q.poll();
                  //parent的左子节点
                  if (!nodes[i].equals(NULL)) {
                      parent.left = new TreeNode(Integer.parseInt(nodes[i]));
                      q.offer(parent.left);
                  } else {
                      parent.left = null;
                  }
                  i++;
                  //parent的右子节点
                  if (!nodes[i].equals(NULL)) {
                      parent.right = new TreeNode(Integer.parseInt(nodes[i]));
                      q.offer(parent.right);
                  } else {
                      parent.right = null;
                  }
                  i++;
              }
              return root;
          }
      }