Binary Tree Serialization

Binary Tree Serialization.png

解題思路 ：

基本靠 queue 解決兩個 function

1. serialize:
   先把 root 放入 queue 在用 !Q.empty() 做為結束的條件執行 while loop 不停地把 queue front 拿出來檢查 null 的話寫入 #, 否則寫入數值(先轉為 string type) 如果此點不是 null 就同時把 left 跟 right child 都推入 queue 最後結束循環以後 把尾端的 # 都略過拿到前面的 substr 即可

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

};