297. Serialize and Deserialize Binary Tree

题目描述和难度

  • 题目描述：

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

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

示例: 

你可以将以下二叉树：

    1
   / \
  2   3
     / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"

提示: 这与LeetCode目前使用的方式一致，详情请参阅 how LeetCode OJ serializes a binary tree。你并非必须采取这种方式，你也可以创造性的用其他的方式解决这个问题。

说明: 不要使用类的成员/全局/静态变量来存储状态机，你的序列化和反序列化算法应该是无状态机的。

思路分析

求解关键：利用前序遍历，就可以序列化一个二叉树，同样，利用反序列化，也可以将一个字符串反序列化为一棵二叉树。

参考解答

参考解答1

import java.util.LinkedList;

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 "";
        }
        StringBuilder builder = new StringBuilder();
        preOrder(root, builder);
        return builder.toString();
    }

    private void preOrder(TreeNode node, StringBuilder builder) {
        if (node == null) {
            builder.append("#");
            builder.append(",");
            return;
        }
        builder.append(node.val);
        builder.append(",");
        preOrder(node.left, builder);
        preOrder(node.right, builder);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }
        LinkedList<String> queue = new LinkedList<>();
        String[] split = data.split(",");
        for(String s:split){
            queue.addLast(s);
        }
        return preOrder(queue);
    }

    private TreeNode preOrder(LinkedList<String> queue ) {
        if (queue.isEmpty()) {
            return null;
        }
        String s = queue.removeFirst();
        if("#".equals(s)){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(s));
        root.left = preOrder(queue);
        root.right =  preOrder(queue);
        return root;
    }


    //       1
    //     2   3
    //    4 5 6 7
    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);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);

        node1.left = node2;
        node1.right = node3;

        node2.left = node4;
        node2.right = node5;

        node3.left = node6;
        node3.right = node7;

        Codec codec = new Codec();
        String serialize = codec.serialize(node1);
        System.out.println(serialize);
    }
}

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

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0297-serialize-and-deserialize-binary-tree ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。