模拟Leetcode通过字符串生成二叉树

二叉树的反序列化

通过一个字符串来实现构造一棵二叉树, 方便在leetcode刷题时进行本地调试

例题

297. 二叉树的序列化与反序列化

实现方案

代码逻辑:

1. 将字符串中的数据提取出来, 存放到vector容器中
2. 使用索引i来控制遍历容器中的数据
3. 使用queue来辅助层次遍历, 每次在加入队列的时候创建节点, 在d出队列的时候为该节点的left指针和right指针赋值

注意事项:

• vector中会保存"null"字符串, 但是queue中只保存非"null"对应的节点
• 在queue每次d出节点时, 索引i指向的为当前节点的左子节点对应的字符串, 可能为"null". 在执行i++之后便会对应到当前节点的右子节点.
• 经过两次i++后, 索引i对应的正好是下一个d出节点的左子节点
• 给出的字符串可能省略了最后的一堆连续的"null", 所以使用if(i < vec_string.size())进行判断

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};



TreeNode *deserialize(const vector &vec_string) {

    const string FLAG = "null";
    /**
     * 队列中保存的值都是非null节点
     */
    queue queue;
    TreeNode *root = new TreeNode(stoi(vec_string[0]));
    queue.push(root);
    int i = 1;
    while (!queue.empty()) {
        int size = queue.size();
        while (size--) {
            TreeNode *peek = queue.front();
            queue.pop();
            if (i < vec_string.size()) {
                //左子节点
                if (vec_string[i] != FLAG) {
                    queue.push(new TreeNode(stoi(vec_string[i])));
                    peek->left = queue.back();
                }
                i++;
            }
            if (i < vec_string.size()) {
                //由于上面i++,因此此时指向右子节点
                if (vec_string[i] != FLAG) {
                    queue.push(new TreeNode(stoi(vec_string[i])));
                    peek->right = queue.back();
                }
                i++;
            }

        }
    }
    return root;
}



TreeNode *deserialize(string data) {
    vector vec_string;
    string word;
    for (int i = 0; i <= data.size(); i++) {
        if (i == data.size() || data[i] == ',') {
            vec_string.push_back(word);
            word.clear();
        } else {
            word += data[i];
        }
    }
    return deserialize(vec_string);
}