文章目錄

• 題目
• 思路
• • 問題一
  • 問題二
• 代碼實現(xiàn)

---

題目

請實現(xiàn)兩個函數(shù)，分別用來序列化和反序列化二叉樹。

設(shè)計一個算法來實現(xiàn)二叉樹的序列化與反序列化。不限定序列 / 反序列化算法執(zhí)行邏輯，你只需要保證一個二叉樹可以被序列化為一個字符串并且將這個字符串反序列化為原始的樹結(jié)構(gòu)。

以上圖為例：

輸入： root = [1,2,3,null,null,4,5]
輸出：[1,2,3,null,null,4,5]

---

思路

兩個問題：

序列化是以怎樣的順序？

反序列化是如何進行的？

其實這兩個問題也就是讓人剛讀完題感到無從下手的原因。首先解決第一個問題：

問題一

遍歷樹無非四種方式——前序、中序、后序、層序。

非常容易得出，本題是按照層序遍歷進行的。那么序列化的難點在哪？在于細節(jié)實現(xiàn)。

題中描述：不限定序列 / 反序列化算法執(zhí)行邏輯，你只需要保證一個二叉樹可以被序列化為一個字符串并且將這個字符串反序列化為原始的樹結(jié)構(gòu)。
說人話就是 空指針不一定要用null表示，示例中的 [] 和 ， 你也可以用別的符號表示，甚至可以不用任何符號（當然逗號盡量不要省去，可以換成別的符號比如空格，主要是必須要有符號來分割節(jié)點，否則無法辨別一串字符到底代表幾個節(jié)點）。

我的選擇是用 ~ 表示 空指針，[] 和 , 保留不變。

要注意幾個細節(jié)：

root為空指針時直接返回[]。

用來保存序列化內(nèi)容的字符串最好在初始化的時候就加上[，在BFS過程中添加的話費時費力。

通過BFS實現(xiàn)層序遍歷。

將節(jié)點加入字符串時順便把，也加進去。

如果節(jié)點為空指針，則向字符串中加入~，。

記得刪除最后一個，。

BFS結(jié)束后記得添加]。

問題二

以示例中為例，得到的序列化（設(shè)為nodes）應(yīng)為：

[1,2,3, ~ , ~ ,4,5,~ , ~ , ~ , ~]

觀察可知，規(guī)律為：

初始化兩個變量 j=0 和 pos=1（0和1指的是節(jié)點下標）。

有這樣的關(guān)系nodes[j]->left=nodes[pos++]; nodes[j]->right=nodes[pos++];（順序不能改變）。

需要注意的細節(jié)：

首先要剝離序列化中的[。

遍歷序列化字符串，遇到 ， 之前的為一個節(jié)點（每個節(jié)點用逗號分隔）。

最后一個節(jié)點用 ] 分割。

---

代碼實現(xiàn)

/*** Definition for a binary tree node.* 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) {if(!root) return "[]";string res("[");queue<TreeNode*> que;que.push(root);while(!que.empty()){TreeNode* node = que.front();que.pop();if(node){res.append(to_string(node->val) + ",");que.push(node->left);que.push(node->right);}else res.append("~,");}res.erase(res.size()-1);res.append("]");//cout << res << endl;return res;}// Decodes your encoded data to tree.TreeNode* deserialize(string data) {if(data=="[]") return nullptr;vector<TreeNode*> nodes;int i = 1;//剝離'['while(i < data.size()){string stmp = "";while(data[i]!=',' && data[i]!=']'){stmp += data[i];i++;}if(stmp == "~"){nodes.push_back(nullptr);}else{int temp = stoi(stmp);TreeNode* node = new TreeNode(temp);//string轉(zhuǎn)intnodes.push_back(node);}i++;}int pos = 1;//數(shù)組構(gòu)成二叉樹映射關(guān)系for(int j = 0; j < nodes.size(); j++){if(!nodes[j]) continue;nodes[j]->left = nodes[pos++];nodes[j]->right = nodes[pos++];}return nodes[0];} };// Your Codec object will be instantiated and called as such: // Codec codec; // codec.deserialize(codec.serialize(root));

總結(jié)

以上是生活随笔為你收集整理的LeetCode——二叉树序列化与反序列化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。