Title source

• leetcode

Title Description

、

title

The essence of binary tree serialization is to encode it , What is more important is to code its structure . You can traverse the tree to complete the above tasks . There are generally two strategies ： Breadth first search and depth first search

• Breadth first search can traverse all nodes from top to bottom according to the hierarchy
• Depth first search can start from a root node , All the way to a leaf , And then back to the root , Reach another branch . According to the root node 、 The relative order between the left and right nodes , The depth first search strategy can be further divided into ：
  • The first sequence traversal
  • In the sequence traversal
  • After the sequence traversal

Depth-first search

serialize ：

• Recursively traverse a tree , Focus on the current node , The traversal of its subtree is completed by recursion ：“serialize function , Please help me serialize my left and right subtrees , I'll wait for your return , Splice it again .”
• Select preorder traversal , Because root | Left | Right root ∣ Left ∣ Right The order of printing , When deserializing, it is easier to locate the value of the root node .
• encounter null Nodes are also translated into specific symbols , I didn't know this was... Until I deserialized it null.

Deserialization

• The serialized string traversed by the preamble , Like the one on the right below ：

• Defined function buildTree Used to restore binary tree , Pass in... Converted from serialized string list Array .
• one by one pop Out list First item of , Build the root node of the current subtree , Along list, The build order is the root node , The left subtree , Right subtree .
  • If the pop-up character is “X”, Then return to null node .
  • If the pop-up character is a numeric value , Create root node , And recursive construction root Right and left subtrees , Finally back to root.
    

class Codec  {
    

    static TreeNode *buildTree( std::list<std::string> & strList){
    
        std::string strtmp = strList.front();
        strList.pop_front();
        if(strtmp == "X"){
    
            return NULL;
        }
        TreeNode *node = new TreeNode(stoi(strtmp));
        node->left = buildTree(strList);
        node->right = buildTree(strList);
        return node;
    }

    static std::list<std::string> split(std::string & data){
    
        int len = data.size();
        std::string curr;
        std::list<std::string> dataArray;
        for(char & ch : data){
    
            if(ch == ','){
    
                dataArray.push_back(curr);
                curr.clear();
            }else{
    
                curr.push_back(ch);
            }
        }
        if(!curr.empty()){
    
            dataArray.push_back(curr);
            curr.clear();
        }
        return dataArray;
    }
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
    
        if(root == NULL){
      //  Traversing  null  node 
            return "X";
        }
        std::string left = serialize(root->left);
        std::string right = serialize(root->right);
        return std::to_string(root->val) + "," + left + "," + right;   //  Press   root , Left , Right   String concatenation 
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
    
        list<string> list = split(data);
       TreeNode* res = buildTree(list);
        return res;
    }
};

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) {
    }
};
class Codec  {
    
    void serialize(TreeNode *root, ostringstream &out) {
    
        if(root){
    
            out << root->val << ' ';
            serialize(root->left, out);
            serialize(root->right, out);
        }else{
    
            out << "# ";
        }
    }

    TreeNode *deserialize(istringstream &in){
    
        std::string val;
        in >> val;
        if(val == "#"){
    
            return nullptr;
        }
        TreeNode *root = new TreeNode(stoi(val));
        root->left = deserialize(in);
        root->right = deserialize(in);
        return root;
    }
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
    
        std::ostringstream out;
        serialize(root, out);
        return out.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
    
        std::istringstream in(data);
        return deserialize(in);
    }
};

Breadth first search

serialize

• Maintain a queue , Initially let the root node join the team , Investigate the node of the team ：
  • If the node out of the queue is NULL, take x push res
  • If the node out of the queue is a value , Push node values into res, And put its left and right nodes in the queue
    - Child node null Also included , It corresponds to “X”, To be recorded , It just has no child nodes to list
• List 、 List out … Until the queue is empty , Just traverse all nodes ,res Build it , Just turn it into a string .

Deserialization

The picture below is BFS The resulting serialized string , and DFS The difference , It's layer upon layer . Except that the first is the value of the root node , Other node values are paired , Corresponding to the left and right child nodes .

• Still turn to list Array , With a pointer cursor Start scanning from the second item .
• At first , use list[0] Build the root node , And let the root node be listed
• Node dequeue , here cursor Point to its left child node value ,cursor+1 Point to its right child node value .
  • If the child node value is a numeric value , Then create the node , And recognize your father , At the same time, he is also a father , List .
  • If the child node value is ‘X’, Nothing to do , Because of the father's left and right It is null
• so , All real nodes will walk through the queue , Take your son out of the line

class Codec  {
    
    
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
    
        std::ostringstream out;
        std::queue<TreeNode*> q;
        if(root){
    
            q.push(root);
        }
        while (!q.empty()){
    
            TreeNode *t = q.front(); q.pop();
            if(t){
    
                out << t->val << ' ';
                q.push(t->left);
                q.push(t->right);
            }else{
    
                out <<"# ";
            }
        }
        return out.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
    
        if(data.empty()){
    
            return nullptr;
        }
        std::istringstream in(data);
        std::queue<TreeNode *>q;
        std::string val;
        in >> val;
        TreeNode *res = new TreeNode(stoi(val)), *curr = res;
        q.push(curr);
        while (!q.empty()){
    
            TreeNode *t = q.front(); q.pop();
            if(!(in >> val)){
    
                break;
            }
            if(val != "#"){
    
                curr = new TreeNode(stoi(val));
                q.push(curr);
                t->left = curr;
            }
            if(!(in >> val)){
    
                break;
            }
            if(val != "#"){
    
                curr = new TreeNode(stoi(val));
                q.push(curr);
                t->right = curr;
            }
        }
        return res;
    }
};