本文涉及知識點

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

LeetCode297. 二叉樹的序列化與反序列化

序列化是將一個數(shù)據(jù)結構或者對象轉換為連續(xù)的比特位的操作，進而可以將轉換后的數(shù)據(jù)存儲在一個文件或者內存中，同時也可以通過網(wǎng)絡傳輸?shù)搅硪粋€計算機環(huán)境，采取相反方式重構得到原數(shù)據(jù)。
請設計一個算法來實現(xiàn)二叉樹的序列化與反序列化。這里不限定你的序列 / 反序列化算法執(zhí)行邏輯，你只需要保證一個二叉樹可以被序列化為一個字符串并且將這個字符串反序列化為原始的樹結構。
提示: 輸入輸出格式與 LeetCode 目前使用的方式一致，詳情請參閱 LeetCode 序列化二叉樹的格式。你并非必須采取這種方式，你也可以采用其他的方法解決這個問題。
示例 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ù)在范圍 [0, 104] 內
-1000 <= Node.val <= 1000

廣度優(yōu)先搜索

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

保存（序列化）

que記錄待處理的節(jié)點。vector v記錄各節(jié)點值對應的字符串，空節(jié)點對應空字符串。任意節(jié)點只有0個或1個父節(jié)點，所以無需visit數(shù)組，避免重復處理。
初始根節(jié)點入隊，按順序從que取節(jié)點，如果為空，則v追加空串。
否則：root的值轉成字符串追加到v中。左右子節(jié)點入隊。
v轉成成字符串，中間用逗號隔開。

讀取（反序列化)

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

代碼

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)先

也不是很麻煩。前序遍歷，用括號括起來一個子樹，可讀性似乎好些。

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;}
};

擴展閱讀

視頻課程

先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

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

相關推薦

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

測試環(huán)境

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