{"id":316,"date":"2017-09-17T19:55:45","date_gmt":"2017-09-18T02:55:45","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=316"},"modified":"2018-08-31T12:50:15","modified_gmt":"2018-08-31T19:50:15","slug":"leetcode-297-serialize-and-deserialize-binary-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-297-serialize-and-deserialize-binary-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 297. Serialize and Deserialize Binary Tree"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 297. Serialize and Deserialize Binary Tree - \u5237\u9898\u627e\u5de5\u4f5c EP59\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/JL4OjKV_pGE?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>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.<\/p>\n<p>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.<\/p>\n<p>For example, you may serialize the following tree<\/p>\n<pre class=\"\">    1\r\n   \/ \\\r\n  2   3\r\n     \/ \\\r\n    4   5\r\n<\/pre>\n<p>as\u00a0<code>\"[1,2,3,null,null,4,5]\"<\/code>, just the same as\u00a0<a href=\"https:\/\/leetcode.com\/faq\/#binary-tree\">how LeetCode OJ serializes a binary tree<\/a>. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.<\/p>\n<p><b>Note:<\/b>\u00a0Do not use class member\/global\/static variables to store states. Your serialize and deserialize algorithms should be stateless.<\/p>\n<p><a href=\"https:\/\/leetcode.com\/problems\/serialize-and-deserialize-binary-tree\/description\/\">https:\/\/leetcode.com\/problems\/serialize-and-deserialize-binary-tree\/description\/<\/a><\/p>\n<p><strong>Idea:<\/strong><\/p>\n<p>Recursion<\/p>\n<p>Time Complexity O(n)<\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/297-ep59-1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-321\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/297-ep59-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/297-ep59-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/297-ep59-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/297-ep59-1-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/297-ep59-1-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/297-ep59-2.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-320\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/297-ep59-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/297-ep59-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/297-ep59-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/297-ep59-2-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/297-ep59-2-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<h1><strong>Solution 1: ASCII<\/strong><\/h1>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 39 ms\r\nclass Codec {\r\npublic:\r\n\r\n    \/\/ Encodes a tree to a single string.\r\n    string serialize(TreeNode* root) {\r\n        ostringstream out;\r\n        serialize(root, out);\r\n        return out.str();\r\n    }\r\n\r\n    \/\/ Decodes your encoded data to tree.\r\n    TreeNode* deserialize(string data) {\r\n        istringstream in(data);\r\n        return deserialize(in);\r\n    }\r\nprivate:\r\n    void serialize(TreeNode* root, ostringstream&amp; out) {\r\n        if (!root) {\r\n            out &lt;&lt; \"# \";\r\n            return;\r\n        }        \r\n        out &lt;&lt; root-&gt;val &lt;&lt; \" \";\r\n        serialize(root-&gt;left, out);\r\n        serialize(root-&gt;right, out);\r\n    }\r\n    \r\n    TreeNode* deserialize(istringstream&amp; in) {\r\n        string val;\r\n        in &gt;&gt; val;\r\n        if (val == \"#\") return nullptr;        \r\n        TreeNode* root = new TreeNode(stoi(val));        \r\n        root-&gt;left = deserialize(in);\r\n        root-&gt;right = deserialize(in);        \r\n        return root;\r\n    }\r\n};\r\n<\/pre>\n<\/div><\/div>\n<h1><strong>Solution 2: Binary<\/strong><\/h1>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 23 ms (beat 98.07%)\r\nclass Codec {\r\npublic:\r\n\r\n    \/\/ Encodes a tree to a single string.\r\n    string serialize(TreeNode* root) {\r\n        ostringstream out;\r\n        serialize(root, out);\r\n        return out.str();\r\n    }\r\n\r\n    \/\/ Decodes your encoded data to tree.\r\n    TreeNode* deserialize(string data) {\r\n        istringstream in(data);\r\n        return deserialize(in);\r\n    }\r\nprivate:\r\n    enum STATUS {\r\n        ROOT_NULL = 0x0,\r\n        ROOT = 0x1,\r\n        LEFT = 0x2,\r\n        RIGHT = 0x4\r\n    };\r\n    \r\n    void serialize(TreeNode* root, ostringstream&amp; out) {\r\n        char status = 0;\r\n        if (root) status |= ROOT;\r\n        if (root &amp;&amp; root-&gt;left) status |= LEFT;\r\n        if (root &amp;&amp; root-&gt;right) status |= RIGHT;\r\n        out.write(&amp;status, sizeof(char));        \r\n        if (!root) return;\r\n        out.write(reinterpret_cast&lt;char*&gt;(&amp;(root-&gt;val)), sizeof(root-&gt;val));\r\n        if (root-&gt;left) serialize(root-&gt;left, out);\r\n        if (root-&gt;right) serialize(root-&gt;right, out);\r\n    }\r\n    \r\n    TreeNode* deserialize(istringstream&amp; in) {\r\n        char status;\r\n        in.read(&amp;status, sizeof(char));\r\n        if (!status &amp; ROOT) return nullptr;\r\n        auto root = new TreeNode(0);\r\n        in.read(reinterpret_cast&lt;char*&gt;(&amp;root-&gt;val), sizeof(root-&gt;val));        \r\n        root-&gt;left = (status &amp; LEFT) ? deserialize(in) : nullptr;\r\n        root-&gt;right = (status &amp; RIGHT) ? deserialize(in) : nullptr;\r\n        return root;\r\n    }\r\n};\r\n\r\n\/\/ Your Codec object will be instantiated and called as such:\r\n\/\/ Codec codec;\r\n\/\/ codec.deserialize(codec.serialize(root));<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++ (string)<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 23 ms (&lt;98.13%)\r\nclass Codec {\r\npublic:\r\n\r\n    \/\/ Encodes a tree to a single string.\r\n    string serialize(TreeNode* root) {\r\n        string s;\r\n        serialize(root, s);\r\n        return s;\r\n    }\r\n\r\n    \/\/ Decodes your encoded data to tree.\r\n    TreeNode* deserialize(string data) { \r\n        int pos = 0;\r\n        return deserialize(data, pos);\r\n    }\r\nprivate:\r\n    enum STATUS {\r\n        ROOT_NULL = 0x0,\r\n        ROOT = 0x1,\r\n        LEFT = 0x2,\r\n        RIGHT = 0x4\r\n    };\r\n    \r\n    void serialize(TreeNode* root, string&amp; s) {\r\n        char status = ROOT_NULL;\r\n        if (root) status |= ROOT;\r\n        if (root &amp;&amp; root-&gt;left) status |= LEFT;\r\n        if (root &amp;&amp; root-&gt;right) status |= RIGHT;\r\n        s.push_back(status);\r\n        if (!root) return;\r\n        s.append(reinterpret_cast&lt;char*&gt;(&amp;root-&gt;val), sizeof(root-&gt;val));\r\n        if (root-&gt;left) serialize(root-&gt;left, s);\r\n        if (root-&gt;right) serialize(root-&gt;right, s);\r\n    }\r\n    \r\n    TreeNode* deserialize(const string&amp; s, int&amp; pos) {\r\n        char status = s[pos++];\r\n        if (!status) return nullptr;\r\n        TreeNode* root = new TreeNode(0);\r\n        memcpy(&amp;root-&gt;val, s.data() + pos, sizeof(root-&gt;val));\r\n        pos += sizeof(root-&gt;val);  \r\n        root-&gt;left = (status &amp; LEFT) ? deserialize(s, pos) : nullptr;\r\n        root-&gt;right = (status &amp; RIGHT) ? deserialize(s, pos) : nullptr;\r\n        return root;\r\n    }\r\n};<\/pre>\n<\/div><\/div>\n<h1><strong>Related Problems<\/strong><\/h1>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-449-serialize-and-deserialize-bst\/\">LeetCode 449. Serialize and Deserialize BST<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Problem: Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[39,93,217,94],"class_list":["post-316","post","type-post","status-publish","format-standard","hentry","category-tree","tag-binary","tag-conversion","tag-hard","tag-serialization","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/316","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=316"}],"version-history":[{"count":11,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/316\/revisions"}],"predecessor-version":[{"id":3796,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/316\/revisions\/3796"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=316"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=316"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=316"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}