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

骑猪看日落 2022-06-08 14:37 169阅读 0赞

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 331. Verify Preorder Serialization of a Binary Tree] 和 [leetcode 654. Maximum Binary Tree 构造最大二叉树][leetcode 654. Maximum Binary Tree] 一起学习

建议和[leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal 中前序构造BST][leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal _BST] 和 [leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal 中后序构造BST][leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal _BST] 和[leetcode 449. Serialize and Deserialize BST 二叉搜索树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));

[leetcode 331. Verify Preorder Serialization of a Binary Tree]: http://blog.csdn.net/jackzhang_123/article/details/78151329
[leetcode 654. Maximum Binary Tree]: http://blog.csdn.net/jackzhang_123/article/details/78865619
[leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal _BST]: http://blog.csdn.net/jackzhang_123/article/details/77977697
[leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal _BST]: http://blog.csdn.net/jackzhang_123/article/details/77977904
[leetcode 449. Serialize and Deserialize BST _BST]: http://blog.csdn.net/jackzhang_123/article/details/78760997