Given a normal binary tree, write a function to serialize the tree into a string representation (returning the string), and also a function to deserialize a serialized string into the original binary tree.

Question

Anónimo · Accepted Answer

/** implemented by traversing a binary tree in level order, with double-ended queue as assistant storages. */

#include 
#include 
#include 

struct BinTreeNode {
    int val;
    BinTreeNode *left, *right;

    BinTreeNode() {}

    BinTreeNode(int v, BinTreeNode *l = NULL, BinTreeNode *r = NULL):
        val(v), left(l), right(r)
    {}
};

void bin_tree_to_str(BinTreeNode *root, std::string& str)
{
    if (root == NULL) return;

    std::deque que;
    BinTreeNode *p;

    que.push_back(root);

    str.append(std::to_string(root->val));

    while (!que.empty()) {
        //undef NDEBUG
        //std::cout val left == NULL && p->right == NULL) continue;

        str.append("L");

        if (p->left) {
            que.push_back(p->left);
            str.append(std::to_string(p->left->val));
        } else {
            str.append("#");
        }

        str.append("R");

        if (p->right) {
            que.push_back(p->right);
            str.append(std::to_string(p->right->val));
        } else {
            str.append("#");
        }
    }

    std::cout  que;
    size_t i, j, l;

    for (i = 0, j = 0, l = str.size();
         i  que2;
    std::string str_val;
    BinTreeNode *root, *left, *right;
    BinTreeNode *temp;

    str_val = que.front();
    que.pop_front();

    root = temp = new BinTreeNode(std::stoi(str_val));

    que2.push_back(temp);

    //while (!que2.empty()) {
    while (!que.empty()) {
    //for (i = 0, l = (que.size() - 1) / 2; i left = left;
        temp->right = right;

        if (left) que2.push_back(left);
        if (right) que2.push_back(right);
    }

    return root;
}

Anónimo · Answer

Uu

Meta

Pregunta de entrevista de Meta

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo