[!note]

This post is using web parser project called Nearlay to verify the parsing process. You can paste the Nearlay grammar definition file into the Nearlay Playground to test it out in your web browser.

Mark End of Sub-Tree

@builtin "whitespace.ne"
@builtin "string.ne"
@builtin "number.ne"

@{%
function de_array(d) {
    if (d.length > 1) {
        throw Error("You can't de_array list with more than one elem!")
    }
    return d[0];
}

function remove_null(d) {
    return d.filter(elem => elem !== null);
}

function tree_processor(d) {
    let obj = {};
    obj.val = d[0];
    
    if(d[1] != null) {
        obj.left = d[1][1];
    }
    if(d[2] != null) {
        obj.right = d[2][1];
    }
    
    return obj;
}
%}

tree -> 
"n" {% d => (null) %}
| leaf ("l" tree "p"):? ("r" tree "p"):? {% tree_processor %}

leaf -> unsigned_int {% de_array %}

Pairing L & R Sub-Tree

@builtin "whitespace.ne"
@builtin "string.ne"
@builtin "number.ne"

@{%
function de_array(d) {
    if (d.length > 1) {
        throw Error("You can't de_array list with more than one elem!")
    }
    return d[0];
}

function remove_null(d) {
    return d.filter(elem => elem !== null);
}

function tree_processor(d) {
    let obj = {};
    
    obj.val = d[0];
    
    if(d[1] != null) {
        obj.left = d[1][1];
        obj.right = d[1][3];
    }
    
    return obj;
}
%}

tree -> 
"n" {% d => (undefined) %}
| leaf ("l" tree "r" tree):? {% tree_processor %}

leaf -> unsigned_int {% de_array %}

This approach doesn't allow L and R marks to appear separately. By adding this rule, we could get away of p mark in previous version.

Code Implementation

AcWing - Serialize Binary Tree

#include<iostream>
#include<string>
#include<sstream>
#include<queue>
#include<vector>

using std::string;
using std::stringstream;
using std::queue, std::vector;
using std::cout, std::endl;

class Solution {
    void push_children_to_queue(TreeNode* node, queue<TreeNode*>& queue) {
        if (node == nullptr) {
            queue.push(nullptr);
            queue.push(nullptr);
            return;
        }

        queue.push(node->left);
        queue.push(node->right);
    }

    void _serialize(TreeNode* root, stringstream& ss) {
        if (root == nullptr) {
            ss << 'n';
            return;
        }

        ss << root->val;

        if (root->left || root->right) {
            ss << 'l';
            _serialize(root->left, ss);

            ss << 'r';
            _serialize(root->right, ss);
        }
    }

    // 1l2lnr3rn
    void _deserialize(TreeNode*& root, stringstream& ss) {
        // todo: does eof() work with stringstream?
        if (ss.eof()) {
            root = nullptr;
            return;
        }
        if (ss.peek() == 'n') {
            ss.ignore();
            root = nullptr;
            return;
        }

        int val = 0;
        ss >> val;

        root = new TreeNode(val);
        if (ss.peek() == 'l') {
            if (ss.peek() != 'l') {
                cout << "Expected: l, got: " << char(ss.peek());
                exit(-1);
            }
            ss.ignore(); // ignore l
            _deserialize(root->left, ss);
            if (ss.peek() != 'r') {
                cout << "Expected: r, got: " << char(ss.peek());
                exit(-1);
            }
            ss.ignore(); // ignore r
            _deserialize(root->right, ss);
        }
    }

    void _show(vector<char>& directions, TreeNode* node) {
        if (node == nullptr) {
            return;
        }

        directions.push_back('r');
        _show(directions, node->right);
        directions.pop_back();

        int cur_layer = directions.size();
        for (int i = 1; i <= cur_layer - 2; ++i) {
            if (directions[i] != directions[i + 1]) {
                cout << "|   ";
            }
            else {
                cout << "    ";
            }
        }
        if (directions.back() == 'l') {
            cout << "+---";
        }
        else if (directions.back() == 'r') {
            cout << "+---";
        }
        cout << node->val << endl;


        directions.push_back('l');
        _show(directions, node->left);
        directions.pop_back();
    }

public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        stringstream ss;
        _serialize(root, ss);
        return ss.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        stringstream ss(data);
        TreeNode* root = nullptr;
        _deserialize(root, ss);
        return root;
    }

    void show(TreeNode* tree) {
        vector<char> directions;
        directions.push_back('-');
        _show(directions, tree);
    }
};