本文涉及知識(shí)點(diǎn)

深度優(yōu)先搜索 廣度優(yōu)先搜索
深度優(yōu)先搜索匯總
圖論知識(shí)匯總

LeetCode297. 二叉樹(shù)的序列化與反序列化

序列化是將一個(gè)數(shù)據(jù)結(jié)構(gòu)或者對(duì)象轉(zhuǎn)換為連續(xù)的比特位的操作，進(jìn)而可以將轉(zhuǎn)換后的數(shù)據(jù)存儲(chǔ)在一個(gè)文件或者內(nèi)存中，同時(shí)也可以通過(guò)網(wǎng)絡(luò)傳輸?shù)搅硪粋€(gè)計(jì)算機(jī)環(huán)境，采取相反方式重構(gòu)得到原數(shù)據(jù)。
請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法來(lái)實(shí)現(xiàn)二叉樹(shù)的序列化與反序列化。這里不限定你的序列 / 反序列化算法執(zhí)行邏輯，你只需要保證一個(gè)二叉樹(shù)可以被序列化為一個(gè)字符串并且將這個(gè)字符串反序列化為原始的樹(shù)結(jié)構(gòu)。
提示: 輸入輸出格式與 LeetCode 目前使用的方式一致，詳情請(qǐng)參閱 LeetCode 序列化二叉樹(shù)的格式。你并非必須采取這種方式，你也可以采用其他的方法解決這個(gè)問(wèn)題。
示例 1：
輸入：root = [1,2,3,null,null,4,5]

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

提示：
樹(shù)中結(jié)點(diǎn)數(shù)在范圍 [0, 104] 內(nèi)
-1000 <= Node.val <= 1000

廣度優(yōu)先搜索

用深度優(yōu)先搜索也可以，只是麻煩得多。
按樹(shù)的層次存取，同層次年長(zhǎng)的在前。為了不處理負(fù)數(shù)，保存時(shí)將數(shù)據(jù)加上1000。讀取后，減去1000。

保存（序列化）

que記錄待處理的節(jié)點(diǎn)。vector v記錄各節(jié)點(diǎn)值對(duì)應(yīng)的字符串，空節(jié)點(diǎn)對(duì)應(yīng)空字符串。任意節(jié)點(diǎn)只有0個(gè)或1個(gè)父節(jié)點(diǎn)，所以無(wú)需visit數(shù)組，避免重復(fù)處理。
初始根節(jié)點(diǎn)入隊(duì)，按順序從que取節(jié)點(diǎn)，如果為空，則v追加空串。
否則：root的值轉(zhuǎn)成字符串追加到v中。左右子節(jié)點(diǎn)入隊(duì)。
v轉(zhuǎn)成成字符串，中間用逗號(hào)隔開(kāi)。

讀取（反序列化)

如果字符串為空，返回null。
建立根節(jié)點(diǎn)，入隊(duì)。
依次出隊(duì)，讀取數(shù)據(jù)。如果數(shù)據(jù)為空。忽略。
數(shù)據(jù)不為空，讀取數(shù)據(jù)到節(jié)點(diǎn)，并為當(dāng)前節(jié)點(diǎn)建立左右子節(jié)點(diǎn)，左右子節(jié)點(diǎn)入隊(duì)。

代碼

class Codec {
public:string serialize(TreeNode* root) {vector<string> v;queue<TreeNode*> que;que.emplace(root);while (que.size()) {auto cur = que.front();que.pop();if (nullptr == cur) { v.emplace_back(""); continue; }v.emplace_back(std::to_string(cur->val+1000));que.emplace(cur->left);que.emplace(cur->right);}string str;for (const auto& s : v) {str += s;str += ',';}str.pop_back();return str;}TreeNode* deserialize(string data) {if ("" == data) { return nullptr; }vector<int> nums;for (int left = 0, r = 0; left < data.length(); left = r) {int num = 0;while ((r < data.length()) && (',' != data[r])) {num = num * 10 + data[r] - '0';r++;}if (left == r) {nums.emplace_back(INT_MIN);}else {nums.emplace_back(num-1000);}r++;}if (',' == data.back()) {nums.emplace_back(INT_MIN);}TreeNode* root = new TreeNode(nums[0]);vector< TreeNode*> nodes;nodes.emplace_back(root);for (int i = 1; i < nums.size(); i++) {if (INT_MIN == nums[i]) {continue;}TreeNode* cur = new TreeNode(nums[i]);nodes.emplace_back(cur);const int inx = (i - 1) / 2;if (1 & i) {nodes[inx]->left = cur;}else {nodes[inx]->right = cur;}}return root;}
};

2023年6月版，就是用的深度優(yōu)先

也不是很麻煩。前序遍歷，用括號(hào)括起來(lái)一個(gè)子樹(shù)，可讀性似乎好些。

class Codec {
public:// Encodes a tree to a single string.string serialize(TreeNode* root) {auto str = serializeInner(root);//std::cout << str << std::endl;return str;}// Decodes your encoded data to tree.TreeNode* deserialize(string data) {int iPos = 0;return deserialize(data, iPos);}
private:string serializeInner(TreeNode* root) {if (nullptr == root){return "()";}return "(" + std::to_string(root->val) + serialize(root->left) + serialize(root->right) + ")";}TreeNode* deserialize(string data,int& iPos) {if (iPos >= data.length()){return nullptr;}iPos++;if ( ')' == data[iPos]){iPos ++;return nullptr;}int iValue = 0;int iSign = 1;if ('-' == data[iPos]){iSign = -1;iPos++;}while (::isdigit(data[iPos])){iValue = iValue * 10 + data[iPos] - '0';iPos++;}iValue *= iSign;TreeNode* p = new TreeNode(iValue);p->left = deserialize(data, iPos);p->right = deserialize(data, iPos);iPos++;return p;}
};

擴(kuò)展閱讀

視頻課程

先學(xué)簡(jiǎn)單的課程，請(qǐng)移步CSDN學(xué)院，聽(tīng)白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成戰(zhàn)斗了，為老板分憂，請(qǐng)學(xué)習(xí)C#入職培訓(xùn)、C++入職培訓(xùn)等課程
https://edu.csdn.net/lecturer/6176

相關(guān)推薦

我想對(duì)大家說(shuō)的話
《喜缺全書算法冊(cè)》以原理、正確性證明、總結(jié)為主。
按類別查閱鄙人的算法文章，請(qǐng)點(diǎn)擊《算法與數(shù)據(jù)匯總》。
有效學(xué)習(xí)：明確的目標(biāo) 及時(shí)的反饋 拉伸區(qū)（難度合適） 專注
聞缺陷則喜(喜缺)是一個(gè)美好的愿望，早發(fā)現(xiàn)問(wèn)題，早修改問(wèn)題，給老板節(jié)約錢。
子墨子言之：事無(wú)終始，無(wú)務(wù)多業(yè)。也就是我們常說(shuō)的專業(yè)的人做專業(yè)的事。
如果程序是一條龍，那算法就是他的是睛

測(cè)試環(huán)境

操作系統(tǒng)：win7 開(kāi)發(fā)環(huán)境： VS2019 C++17
或者 操作系統(tǒng)：win10 開(kāi)發(fā)環(huán)境： VS2022 C++17
如無(wú)特殊說(shuō)明，本算法用**C++**實(shí)現(xiàn)。