二叉树的序列化和反序列化

二叉搜索树是二叉树的一种，也可以使用这种方法。

BFS, 按层序列化和反序列

https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/

这是种什么表示方法？

反序列化

vector<int> nums = {1, 2, 3, -1, -1, 4, 5};
struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};
Node* GetNode(vector<int>& nums)
{
    Node* root = new Node(nums[0]);
    queue<Node*> que;
    que.push(root);
    int k = 1;
    while (k < nums.size()) {
        int n = que.size();
        for (int i = 0; i < n; i++) {
            Node* p = que.front();
            que.pop();
            if (nums[k] == -1 && nums[k + 1] == -1) {
                k+=2;
                continue;
            }
            if (nums[k] != -1) {
                p->left = new Node(nums[k]);
                que.push(p->left);
                cout << p->left->val << ", ";
            }
            k++;
            if (nums[k] != -1) {
                p->right = new Node(nums[k]);
                que.push(p->right);
                cout << p->right->val << ", ";
            }
            k++;
        }
    }
    return root;
}

DFS、前序遍历

https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == nullptr) {
            return "#";
        }
        return to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right);
    }
    TreeNode* rdeserialize(vector<string>& vec, int& index)
    {
        if (vec.size() <= index) {
            return nullptr;
        }
        if (vec[index] == "#") {
            index++;
            return nullptr;
        }
        TreeNode* node = new TreeNode(stoi(vec[index]));
        index++;
        node->left = rdeserialize(vec, index);
        node->right = rdeserialize(vec, index);
        return node;
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        vector<string> vec;
        string tmp;
        for (auto& a : data) {
            if (a == ',') {
                vec.push_back(tmp);
                tmp.clear();
            } else {
                tmp += a;
            }
        }
        if (tmp.size() != 0) {
            vec.push_back(tmp);
        }
        int index = 0;
        TreeNode* root = rdeserialize(vec, index);
        return root;
    }
};
// Your Codec object will be instantiated and called as such:
// Codec* ser = new Codec();
// Codec* deser = new Codec();
// string tree = ser->serialize(root);
// TreeNode* ans = deser->deserialize(tree);
// return ans;