# leetcode 297 Serialize and Deserialize Binary Tree

## 思路

從 LeetCode 原生的作法出發

      5
     / \
    4   7
   /
  3
 /
-1

to `[5,4,7,3,null,null,null,-1]`
再簡潔一點，用 bfs 的相對位置去做 `[5|4,7|3|1<-1]`
算一下複雜度發現複雜度沒變，那還是算了。

而且這題用 DFS 比較好做

把 null 的部份替換成 `#`

      5
     / \
    4   7
   /
  3
 /
-1

to `[5,4,3,-1,#,#,#,#,7]`
配合 stringstream 方便取用, 改成空白鍵
`[5 4 3 -1 # # # # 7]`

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string result{};
        serializeHelper(root, &result);
        return result;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        stringstream input(data);
        return deserializeHelper(input);
    }

private:
    void serializeHelper(const TreeNode* root, string* prev) {
        if (!root) {
            prev->append("# ");
        }
        else {
            prev->append(to_string(root->val).append(" "));
            serializeHelper(root->left, prev);
            serializeHelper(root->right, prev);
        }
    }
    
    TreeNode* deserializeHelper(stringstream& input) {
        string val;
        input >> val;
        if (val == "#") {
            return nullptr;
        }
        else {
            TreeNode* root = new TreeNode(stoi(val));
            root->left = deserializeHelper(input);
            root->right = deserializeHelper(input);
            return root;
        }
    }
};

用 BFS 的話也很簡單，但就是會寫比較長

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        return serializeHelper(root);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        return deserializeHelper(data);
    }
private:
    string serializeHelper(const TreeNode* root) {
        if (root == nullptr)
            return {};
        
        string result{};
        queue<const TreeNode* > bfs({root});
        while (!bfs.empty()) {
            auto cur = bfs.front();
            bfs.pop();
            if (cur == nullptr) {
                result.append("# ");
                continue;
            }
            result.append(to_string(cur->val) + " ");
            bfs.push(cur->left);
            bfs.push(cur->right);
        }
        return result;
    }

    TreeNode* deserializeHelper(const string& data) {
        if (data.empty())
            return nullptr;
        istringstream input(data);
        string Val;
        input >> Val;
        auto root = new TreeNode(stoi(Val));
        queue<TreeNode* > bfs({ root });

        while (!bfs.empty()) {
            auto cur = bfs.front();
            bfs.pop();
            input >> Val;
            if (Val != "#") {
                cur->left = new TreeNode(stoi(Val));
                bfs.push(cur->left);
            }
            input >> Val;
            if (Val != "#") {
                cur->right = new TreeNode(stoi(Val));
                bfs.push(cur->right);
            }
        }
        return root;
    }
};