{"id":7403,"date":"2026-07-21T22:05:55","date_gmt":"2026-07-21T14:05:55","guid":{"rendered":"https:\/\/i007.cc\/wordpress\/?p=7403"},"modified":"2026-07-21T22:05:55","modified_gmt":"2026-07-21T14:05:55","slug":"%e4%ba%8c%e5%8f%89%e6%a0%91%e7%9a%84%e5%ba%8f%e5%88%97%e5%8c%96%e4%b8%8e%e5%8f%8d%e5%ba%8f%e5%88%97%e5%8c%96%ef%bc%88serialize-and-deserialize-binary-tree%ef%bc%89","status":"publish","type":"post","link":"https:\/\/i007.cc\/wordpress\/archives\/7403","title":{"rendered":"\u4e8c\u53c9\u6811\u7684\u5e8f\u5217\u5316\u4e0e\u53cd\u5e8f\u5217\u5316\uff08Serialize and Deserialize Binary Tree\uff09"},"content":{"rendered":"

\u529b\u6263\u7b2c 297 \u9898\u3002\u628a\u4e00\u68f5\u4e8c\u53c9\u6811\u8f6c\u6210\u5b57\u7b26\u4e32\u5b58\u50a8\uff0c\u518d\u628a\u5b57\u7b26\u4e32\u8fd8\u539f\u6210\u539f\u6765\u7684\u6811\u3002<\/p>\n

\n

\u5148\u60f3\u6e05\u695a\u4e00\u4e2a\u95ee\u9898\uff1a\u4e3a\u4ec0\u4e48\u9700\u8981\u8bb0\u5f55\u7a7a\u8282\u70b9\uff1f<\/h4>\n

\u53ea\u8bb0\u5f55\u975e\u7a7a\u8282\u70b9\u7684\u524d\u5e8f\u904d\u5386\u662f 1,2,3<\/code>\uff0c\u4f46\u8fd9\u68f5\u6811\u548c\u53e6\u4e00\u68f5\u6811\u53ef\u80fd\u6709\u76f8\u540c\u7684\u5e8f\u5217\uff1a<\/p>\n

\n
\n
<\/div>\n<\/div>\n
\n
1              1\r\n   \/ \\              \\\r\n  2   3              2\r\n                      \\\r\n                       3<\/pre>\n
 <\/p>\n<\/div>\n<\/div>\n
\u5fc5\u987b\u628a\u7a7a\u8282\u70b9\u4e5f\u5e8f\u5217\u5316\u8fdb\u53bb<\/strong>\uff0c\u624d\u80fd\u552f\u4e00\u8fd8\u539f\u4e00\u68f5\u6811\u3002<\/p>\n
\n
\u6700\u4f18\u89e3\u6cd5\uff1a\u524d\u5e8f\u904d\u5386\uff08DFS\uff09\u2b50<\/h4>\n
\u5e8f\u5217\u5316\u65f6\u524d\u5e8f\u904d\u5386\uff0c\u7a7a\u8282\u70b9\u5199 #<\/code>\uff0c\u8282\u70b9\u95f4\u7528 ,<\/code> \u5206\u9694\u3002\u53cd\u5e8f\u5217\u5316\u65f6\u540c\u6837\u6309\u524d\u5e8f\u987a\u5e8f\u6d88\u8d39\u5b57\u7b26\u4e32\u3002<\/p>\n
\n
\n
<\/div>\n<\/div>\n
cpp<\/div>\n
\n
class Codec {\r\npublic:\r\n    \/\/ \u2500\u2500 \u5e8f\u5217\u5316 \u2500\u2500\r\n    string serialize(TreeNode* root) {\r\n        string res;\r\n        dfs_serialize(root, res);\r\n        return res;\r\n    }\r\n\r\n    void dfs_serialize(TreeNode* node, string& res) {\r\n        if (!node) {\r\n            res += \"#,\";\r\n            return;\r\n        }\r\n        res += to_string(node->val) + \",\";\r\n        dfs_serialize(node->left,  res);\r\n        dfs_serialize(node->right, res);\r\n    }\r\n\r\n    \/\/ \u2500\u2500 \u53cd\u5e8f\u5217\u5316 \u2500\u2500\r\n    TreeNode* deserialize(string data) {\r\n        queue<string> q;\r\n        string token;\r\n        for (char c : data) {\r\n            if (c == ',') { q.push(token); token.clear(); }\r\n            else token += c;\r\n        }\r\n        return dfs_deserialize(q);\r\n    }\r\n\r\n    TreeNode* dfs_deserialize(queue<string>& q) {\r\n        string val = q.front(); q.pop();\r\n        if (val == \"#\") return nullptr;\r\n\r\n        TreeNode* node = new TreeNode(stoi(val));\r\n        node->left  = dfs_deserialize(q);  \/\/ \u5148\u5efa\u5de6\u5b50\u6811\r\n        node->right = dfs_deserialize(q);  \/\/ \u518d\u5efa\u53f3\u5b50\u6811\r\n        return node;\r\n    }\r\n};<\/pre>\n
 <\/p>\n<\/div>\n<\/div>\n
\n
\u4e3a\u4ec0\u4e48\u524d\u5e8f\u904d\u5386\u7279\u522b\u9002\u5408\u8fd9\u9053\u9898\uff1f<\/h4>\n
\u524d\u5e8f\u662f”\u6839 \u2192 \u5de6 \u2192 \u53f3”\uff0c\u5e8f\u5217\u5316\u548c\u53cd\u5e8f\u5217\u5316\u7684\u987a\u5e8f\u5b8c\u5168\u4e00\u81f4<\/strong>\u2014\u2014\u53cd\u5e8f\u5217\u5316\u65f6\u6bcf\u6b21\u4ece\u961f\u5217\u5934\u53d6\u4e00\u4e2a\u503c\uff0c\u5c31\u77e5\u9053\u8fd9\u662f\u5f53\u524d\u5b50\u6811\u7684\u6839\uff0c\u9012\u5f52\u5f80\u4e0b\u5efa\uff0c\u5929\u7136\u5bf9\u5e94\u3002<\/p>\n
\n
\n
<\/div>\n<\/div>\n
\n
\u6811:         1\r\n           \/ \\\r\n          2   3\r\n         \/\r\n        4\r\n\r\n\u5e8f\u5217\u5316: 1,2,4,#,#,#,3,#,#\r\n\r\n\u53cd\u5e8f\u5217\u5316\u8fc7\u7a0b:\r\n\u53d6 1 \u2192 \u6839\u8282\u70b9\r\n  \u53d6 2 \u2192 \u5de6\u5b50\u6811\u6839\r\n    \u53d6 4 \u2192 \u5de6\u5b50\u6811\u6839\r\n      \u53d6 # \u2192 4 \u7684\u5de6\u4e3a null\r\n      \u53d6 # \u2192 4 \u7684\u53f3\u4e3a null\r\n    \u53d6 # \u2192 2 \u7684\u53f3\u4e3a null\r\n  \u53d6 3 \u2192 \u53f3\u5b50\u6811\u6839\r\n    \u53d6 # \u2192 3 \u7684\u5de6\u4e3a null\r\n    \u53d6 # \u2192 3 \u7684\u53f3\u4e3a null\r\n\u8fd8\u539f\u5b8c\u6bd5 \u2713<\/pre>\n
 <\/p>\n<\/div>\n<\/div>\n
\n
\u89e3\u6cd5\u4e8c\uff1aBFS \u5c42\u5e8f\u904d\u5386<\/h4>\n
\n
\n
<\/div>\n<\/div>\n
cpp<\/div>\n
\n
string serialize(TreeNode* root) {\r\n    if (!root) return \"\";\r\n    string res;\r\n    queue<TreeNode*> q;\r\n    q.push(root);\r\n    while (!q.empty()) {\r\n        TreeNode* node = q.front(); q.pop();\r\n        if (!node) { res += \"#,\"; continue; }\r\n        res += to_string(node->val) + \",\";\r\n        q.push(node->left);\r\n        q.push(node->right);\r\n    }\r\n    return res;\r\n}\r\n\r\nTreeNode* deserialize(string data) {\r\n    if (data.empty()) return nullptr;\r\n    \/\/ \u5206\u5272\u5b57\u7b26\u4e32\r\n    vector<string> tokens;\r\n    string token;\r\n    for (char c : data) {\r\n        if (c == ',') { tokens.push_back(token); token.clear(); }\r\n        else token += c;\r\n    }\r\n    int i = 1;\r\n    TreeNode* root = new TreeNode(stoi(tokens[0]));\r\n    queue<TreeNode*> q;\r\n    q.push(root);\r\n    while (!q.empty()) {\r\n        TreeNode* node = q.front(); q.pop();\r\n        if (tokens[i] != \"#\") {\r\n            node->left = new TreeNode(stoi(tokens[i]));\r\n            q.push(node->left);\r\n        }\r\n        i++;\r\n        if (tokens[i] != \"#\") {\r\n            node->right = new TreeNode(stoi(tokens[i]));\r\n            q.push(node->right);\r\n        }\r\n        i++;\r\n    }\r\n    return root;\r\n}<\/pre>\n
 <\/p>\n<\/div>\n<\/div>\n
BFS \u7248\u672c\u66f4\u76f4\u89c2\uff08\u5c31\u662f\u5c42\u5e8f\u6253\u5370\uff09\uff0c\u4f46\u4ee3\u7801\u7565\u957f\uff0c\u53cd\u5e8f\u5217\u5316\u9700\u8981\u989d\u5916\u7ef4\u62a4\u7d22\u5f15\u3002<\/p>\n
\n
\u4e24\u79cd\u89e3\u6cd5\u5bf9\u6bd4<\/h4>\n
\n\n\n\n\n\n\n\n\n
<\/th>\nDFS \u524d\u5e8f<\/th>\nBFS \u5c42\u5e8f<\/th>\n<\/tr>\n<\/thead>\n
\u65f6\u95f4<\/td>\nO(n)<\/td>\nO(n)<\/td>\n<\/tr>\n
\u7a7a\u95f4<\/td>\nO(h) \u9012\u5f52\u6808<\/td>\nO(w) \u961f\u5217\uff08w\u4e3a\u6700\u5927\u5bbd\u5ea6\uff09<\/td>\n<\/tr>\n
\u4ee3\u7801\u7b80\u6d01\u5ea6<\/td>\n\u2605\u2605\u2605\u2605\u2605<\/td>\n\u2605\u2605\u2605<\/td>\n<\/tr>\n
\u9762\u8bd5\u63a8\u8350<\/td>\n\u2705 \u9996\u9009<\/td>\n\u4f5c\u4e3a\u7b2c\u4e8c\u601d\u8def<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n
\u6700\u574f\u60c5\u51b5\u4e0b\uff08\u6ee1\u4e8c\u53c9\u6811\uff09BFS \u961f\u5217\u5bbd\u5ea6 O(n\/2)\uff0cDFS \u6808\u6df1\u5ea6 O(log n)\u2014\u2014DFS \u7a7a\u95f4\u66f4\u4f18\u3002<\/p>\n
\n
\u9762\u8bd5\u65f6\u6700\u5bb9\u6613\u8e29\u7684\u5751<\/h4>\n
\u2460 \u5206\u9694\u7b26\u4e0d\u80fd\u7701<\/strong>\uff1a12<\/code> \u548c 1,2<\/code> \u662f\u4e0d\u540c\u7684\uff0c\u8282\u70b9\u503c\u53ef\u80fd\u662f\u591a\u4f4d\u6570\u751a\u81f3\u8d1f\u6570\uff0c\u5fc5\u987b\u6709\u5206\u9694\u7b26\u3002<\/p>\n
\u2461 \u7a7a\u8282\u70b9\u5fc5\u987b\u5e8f\u5217\u5316<\/strong>\uff1a\u8fd9\u662f\u8fd8\u539f\u552f\u4e00\u6027\u7684\u4fdd\u8bc1\uff0c\u4e0d\u80fd\u53ea\u8bb0\u975e\u7a7a\u8282\u70b9\u3002<\/p>\n
\u2462 \u53cd\u5e8f\u5217\u5316\u7528\u961f\u5217\u800c\u975e\u4e0b\u6807<\/strong>\uff1a\u961f\u5217\u5929\u7136\u652f\u6301\u6309\u5e8f\u6d88\u8d39\uff0c\u4ee3\u7801\u66f4\u7b80\u6d01\uff0c\u4e0d\u5bb9\u6613\u8d8a\u754c\u3002<\/p>\n
\u628a\u8fd9\u4e09\u70b9\u5728\u9762\u8bd5\u91cc\u4e3b\u52a8\u8bf4\u51fa\u6765\uff0c\u6bd4\u76f4\u63a5\u5199\u4ee3\u7801\u66f4\u80fd\u4f53\u73b0\u7406\u89e3\u6df1\u5ea6\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
\u529b\u6263\u7b2c 297 \u9898\u3002\u628a\u4e00\u68f5\u4e8c\u53c9\u6811\u8f6c\u6210\u5b57\u7b26<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","footnotes":""},"categories":[24],"tags":[],"class_list":["post-7403","post","type-post","status-publish","format-standard","hentry","category-value_docs"],"_links":{"self":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7403","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/comments?post=7403"}],"version-history":[{"count":1,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7403\/revisions"}],"predecessor-version":[{"id":7404,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/7403\/revisions\/7404"}],"wp:attachment":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/media?parent=7403"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/categories?post=7403"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/tags?post=7403"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}