題目分析

題目鏈接：449. 序列化和反序列化二叉搜索樹

覺得序列化很簡單，前序遍歷、后序遍歷、中序遍歷、層序遍歷等等。其中得到前序遍歷和后序遍歷是可以通過遞歸解法反序列化的，覺得這樣子做有點復雜。就想著可不可以一次遍歷。一次遍歷的問題在于不知道哪里子孩子為空（因為沒有保存子孩子為空的情況）。所以我就針對性地讓空節點的值為-1。為了方便從字符串中讀取數字，使用了C++中的istringstream。整體的實現還是比較簡潔高效的。

實現代碼

class Codec {
public:// Encodes a tree to a single string.string serialize(TreeNode* root) {queue<TreeNode*> q;string ans;if (root == nullptr) return ans;q.push(root);int cnt;TreeNode *t;while (!q.empty()) {cnt = q.size();while (cnt--) {t = q.front(); q.pop();if (t) {ans.append(std::to_string(t->val));q.push(t->left);q.push(t->right);} else {ans.append("-1");}ans.push_back(' ');}}return ans;}// Decodes your encoded data to tree.TreeNode* deserialize(string data) {std::istringstream is(data);int x, y, cnt;TreeNode *root = nullptr, *t;queue<TreeNode*> q;if (is >> x) {root = new TreeNode(x);q.push(root);while (!q.empty()) {cnt = q.size();while (cnt--) {t = q.front(); q.pop();is >> x >> y;if (x != -1) {t->left = new TreeNode(x);q.push(t->left);}if (y != -1) {t->right = new TreeNode(y);q.push(t->right);}}}}return root;}
};

反思總結

寫完后去看了一眼題解才發現是二叉搜索樹。。。我眼睛是有多瞎。不過二叉搜索樹也沒有什么特別好的優化。

如果用的是中序和前序還原的話，由于二叉搜索樹中序遍歷是有序的性質不用去特意保存中序遍歷。