Binary Tree Serialization.png
解題思路 ：
基本靠 queue 解決兩個 function
serialize:
先把 root 放入 queue 在用 !Q.empty() 做為結束的條件執行 while loop 不停地把 queue front 拿出來檢查 null 的話寫入 #, 否則寫入數值(先轉為 string type) 如果此點不是 null 就同時把 left 跟 right child 都推入 queue 最後結束循環以後 把尾端的 # 都略過拿到前面的 substr 即可deserialize:
關鍵在找到 string 裡面每個數值的 index 範圍 然後取出這個範圍的 substr 作轉換為 int 的動作 最後拿來建立 node 存入 queue 後續其他的 substr 就順勢連接為 left 跟 right child 記得隨時檢查搜索 string 裡的範圍不能超過 string 本身長度
C++ code :
<pre><code>
/**
- Definition of TreeNode:
- class TreeNode {
- public:
int val;TreeNode *left, *right;TreeNode(int val) {this->val = val;this->left = this->right = NULL;}- }
*/
class Solution {
public:
/**
* This method will be invoked first, you should design your own algorithm
* to serialize a binary tree which denote by a root node to a string which
* can be easily deserialized by your own "deserialize" method later.
*/
string serialize(TreeNode *root) {
// write your code here
if(!root) return "";
queue<TreeNode*> Q;
string res = "";
Q.push(root);
while(!Q.empty())
{
TreeNode *tmp = Q.front();
Q.pop();
if(!tmp) res = res + "#,";
else{
res = res + to_string(tmp->val);
res = res + ",";
}
if(tmp)
{
Q.push(tmp->left);
Q.push(tmp->right);
}
}
int end = res.length() -1;
for(int i = res.length() -1; i >= 0; i--)
{
if(res[i] != '#' && res[i] != ',')
{
end = i;
break;
}
}
res = res.substr(0, end + 1);
return res;
}
/**
* This method will be invoked second, the argument data is what exactly
* you serialized at method "serialize", that means the data is not given by
* system, it's given by your own serialize method. So the format of data is
* designed by yourself, and deserialize it here as you serialize it in
* "serialize" method.
*/
int findComma(string data, int start)
{
int i = start;
for(; i < data.length(); i++)
{
if(data[i] == ',') return i;
}
return i;
}
TreeNode *deserialize(string data) {
// write your code here
if(data.length() == 0) return nullptr;
int start_index = 0, comma_index = 0;
comma_index = findComma(data, start_index);
string num = data.substr(start_index, comma_index - start_index);
start_index = comma_index + 1;
int value = stoi(num);
TreeNode *root = new TreeNode(value);
queue<TreeNode*> Q;
Q.push(root);
while(!Q.empty() && start_index < data.length())
{
int n = Q.size();
for(int i = 0; i < n; i++)
{
TreeNode *tmp = Q.front();
Q.pop();
comma_index = findComma(data, start_index);
num = data.substr(start_index, comma_index - start_index);
start_index = comma_index + 1;
if(num[0] != '#') {
value = stoi(num);
TreeNode *left_child = new TreeNode(value);
tmp->left = left_child;
Q.push(left_child);
}
if(start_index >= data.length()) break;
comma_index = findComma(data, start_index);
num = data.substr(start_index, comma_index - start_index);
start_index = comma_index + 1;
if(num[0] != '#') {
value = stoi(num);
TreeNode *right_child = new TreeNode(value);
tmp->right = right_child;
Q.push(right_child);
}
if(start_index >= data.length()) break;
}
}
return root;
}
};
