leetcode 297. Serialize and Deserialize Binary Tree 二叉树的序列化和反序列化 + 深度优先遍历DFS-蒲公英云

leetcode 297. Serialize and Deserialize Binary Tree 二叉树的序列化和反序列化 + 深度优先遍历DFS

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

1
/ \
2 3
/ \
4 5
as “[1,2,3,null,null,4,5]”, just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

题意很简答，就是完成二叉树的序列化和反序列化，序列化很容易错，也就是二叉树的遍历；对于反序列化，也就是把一个字符串转化为一个二叉树，这个还是用同样的思想去做，看了网上的一个答案，才明白原来是这么的简单。

先序遍历的递归解法和层序遍历的非递归解法。先来看先序遍历的递归解法，非常的简单易懂，我们需要接入输入和输出字符串流istringstream和ostringstream，对于序列化，我们从根节点开始，如果节点存在，则将值存入输出字符串流，然后分别对其左右子节点递归调用序列化函数即可。对于去序列化，我们先读入第一个字符，以此生成一个根节点，然后再对根节点的左右子节点递归调用去序列化函数即可，参见代码如下：

建议和leetcode 331. Verify Preorder Serialization of a Binary Tree 二叉树的前序序列验证和 leetcode 654. Maximum Binary Tree 构造最大二叉树一起学习

建议和leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal 中前序构造BST 和 leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal 中后序构造BST 和leetcode 449. Serialize and Deserialize BST 二叉搜索树BST的序列化和反序列化一起学习，疑问做法感觉类似

代码如下：

import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
/*class TreeNode 
{
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
}
*/
/*
 * 这个序列化和反序列化就是通过中序来实现 
 * 要记着这么做
 * */
public class Codec 
{
    private final String delimiter = ",";
    private final String nullNode = "#";
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) 
    {
       StringBuilder builder=new StringBuilder();
       serialize(root,builder);
       return builder.toString();
    }
    /*
     *  中序遍历得到序列化的值
     * */
    private void serialize(TreeNode root, StringBuilder builder)
    {
        if(root==null)
            builder.append(nullNode).append(delimiter);
        else 
        {
            builder.append(root.val).append(delimiter);
            serialize(root.left, builder);
            serialize(root.right, builder);
        }
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data)
    {
        if(data==null || data.length()<=0)
            return null;
        String[] tmp = data.split(delimiter);
        Queue<String> queue=new LinkedList<>();
        Collections.addAll(queue, tmp);
        TreeNode root=deserialize(queue);
        return root;
    }
    private TreeNode deserialize(Queue<String> queue) 
    {
        if(queue==null || queue.size()<=0)
            return null;
        String one=queue.poll();
        if(one.equals(nullNode))
            return null;
        else 
        {
            TreeNode root=new TreeNode(Integer.parseInt(one));
            root.left=deserialize(queue);
            root.right=deserialize(queue);
            return root;
        }   
    }
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

下面是C++的做法，这道题十分的棒们很值得学习

代码如下：

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <string>
#include <climits>
#include <algorithm>
#include <sstream>
#include <functional>
#include <bitset>
#include <numeric>
#include <cmath>
#include <regex>
using namespace std;
/*
struct TreeNode 
{
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
*/
class Codec 
{
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root)
    {
        stringstream ss;
        dfs1(ss,root);
        return ss.str();
    }
    void dfs1(stringstream &ss,TreeNode* root)
    {
        if (root == NULL)
            ss << "#" << " ";
        else
        {
            ss << root->val << " ";
            dfs1(ss,root->left);
            dfs1(ss,root->right);
        }
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data)
    {
        stringstream ss(data);
        return dfs2(ss);
    }
    TreeNode* dfs2(stringstream &ss)
    {
        string one = "";
        ss >> one;
        if (one == "#")
            return NULL;
        else
        {
            TreeNode* root = new TreeNode(stoi(one));
            root->left = dfs2(ss);
            root->right = dfs2(ss);
            return root;
        }
    }
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));