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

题目描述

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

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

解题思路

之前大作业太多搞得一直没时间记一记题，今天写了这个题还不错，tag:二叉树层序遍历、序列化。
搞成序列化的String么，肯定用先中后序遍历一遍然后固定格式输出，然后deserialize的时候递归生成树就行了。但是?偏偏用层序遍历，想不到吧。由于需要用到大量关于字符串组合和拆分的操作，用的JAVA完成。题倒是不难，顺带把很少写反序列化的层序遍历练一下。

源代码

import java.util.LinkedList;
import java.util.Queue;

public class lc297 {

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        node1.left = node2;
        node1.right = node3;
        node2.left = null;
        node2.right = null;
        node3.left = node4;
        node3.right = node5;
        node4.left = null;
        node4.right = null;
        node5.left = null;
        node5.right = null;
        String ser_str = serialize(node1);
        System.out.println(ser_str);
        TreeNode root = deserialize(ser_str);
    }

        // Encodes a tree to a single string.
        public static String serialize(TreeNode root) {
            if (root == null)
                return new String("N");

            Queue<TreeNode> node_que = new LinkedList<>();
            TreeNode front;
            StringBuilder serial_str = new StringBuilder("" + root.val);

            node_que.add(root);
            while(!node_que.isEmpty()){
                front = node_que.remove();

                if (front.left != null) {
                    node_que.add(front.left);
                    serial_str.append(",").append(front.left.val);
                }
                else{
                    serial_str.append(",N");
                }

                if (front.right != null) {
                    node_que.add(front.right);
                    serial_str.append(",").append(front.right.val);
                }
                else{
                    serial_str.append(",N");
                }
            }

            return serial_str.toString();
        }

        // Decodes your encoded data to tree.
        public static TreeNode deserialize(String data) {
            int i = 0;
            String[] elems = data.split(",");
            TreeNode root = TNInitialByStr(elems[0]);
            Queue<TreeNode> node_q = new LinkedList<>();
            if (root == null)
                return null;
            node_q.add(root);
            TreeNode node = null;
            while(!node_q.isEmpty()){
                node = node_q.poll();
                node.left = TNInitialByStr(elems[++i]);
                node.right = TNInitialByStr(elems[++i]);
                if (node.left != null)
                    node_q.add(node.left);
                if (node.right != null)
                    node_q.add(node.right);
            }
            return root;
        }

        public static TreeNode TNInitialByStr(String val){
            if(val.equals("N"))
                return null;
            return new TreeNode(Integer.parseInt(val));
        }
      //Definition for a binary tree node.
      public static class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
         TreeNode(int x) { val = x; }
      }
}

LC格式

/**
 * 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) {
        if (root == null)
            return new String("N");

        Queue<TreeNode> node_que = new LinkedList<>();
        TreeNode front;
        StringBuilder serial_str = new StringBuilder("" + root.val);

        node_que.add(root);
        while(!node_que.isEmpty()){
            front = node_que.remove();

            if (front.left != null) {
                node_que.add(front.left);
                serial_str.append(",").append(front.left.val);
            }
            else{
                serial_str.append(",N");
            }

            if (front.right != null) {
                node_que.add(front.right);
                serial_str.append(",").append(front.right.val);
            }
            else{
                serial_str.append(",N");
            }
        }

        return serial_str.toString();
    }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            int i = 0;
            String[] elems = data.split(",");
            TreeNode root = TNInitialByStr(elems[0]);
            Queue<TreeNode> node_q = new LinkedList<>();
            if (root == null)
                return null;
            node_q.add(root);
            TreeNode node = null;
            while(!node_q.isEmpty()){
                node = node_q.poll();
                node.left = TNInitialByStr(elems[++i]);
                node.right = TNInitialByStr(elems[++i]);
                if (node.left != null)
                    node_q.add(node.left);
                if (node.right != null)
                    node_q.add(node.right);
            }
            return root;
        }

        public TreeNode TNInitialByStr(String val){
            if(val.equals("N"))
                return null;
            return new TreeNode(Integer.parseInt(val));
        }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));