Be creative! Share my C++ solution.


  • 4
    L

    The problem asks me to be creative, so I came up this idea.

    For tree,

        1
       / \
      2   3
         / \
        4   5
       /     \
      6       7
    

    The serialization will be 1,2,N,3,4,5,L,6,R,7,N,N

    • N represents there are no children for the previous node.
    • L represents that the previous node have one left child, and the value of that child comes after it.
    • R represents that there is one right child.

    I use queue to do level traversal, the time complexity should be O(n) for both operations.

    C++ code here:

    class Codec {
    public:
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            if (root == NULL) return "";
            queue<TreeNode *> q;
            q.push(root);
            TreeNode *p;
            string result = to_string(root->val);
            while (!q.empty()) {
                p = q.front();
                q.pop();
                if (p->left && p->right) {
                    q.push(p->left);
                    q.push(p->right);
                    result += "," + to_string(p->left->val) + "," + to_string(p->right->val);
                }
                else if (p->left && !p->right) {
                    q.push(p->left);
                    result += ",L," + to_string(p->left->val);
                }
                else if (!p->left && p->right) {
                    q.push(p->right);
                    result += ",R," + to_string(p->right->val);
                }
                else {
                    result += ",N";
                }
            }
            return result;
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            if (data.length() == 0) return NULL;
            vector<string> nodes = split(data, ',');
            auto it = nodes.begin();
            TreeNode *root = new TreeNode(stoi(*(it++)));
            queue<TreeNode *> q;
            q.push(root);
            while (!q.empty() && it != nodes.end()) {
                TreeNode *p = q.front();
                if (*it == "N") {
                    it++;
                }
                else if (*it == "L") {
                    p->left = new TreeNode(stoi(*(++it)));
                    it++;
                }
                else if (*it == "R") {
                    p->right = new TreeNode(stoi(*(++it)));
                    it++;
                }
                else {
                    p->left = new TreeNode(stoi(*(it++)));
                    p->right = new TreeNode(stoi(*(it++)));
                }
    
                q.pop();
                if (p->left) q.push(p->left);
                if (p->right) q.push(p->right);
            }
            return root;
        }
    
        vector<string> split(string str, char delimiter) {
            vector<string> result;
            int last = 0;
            for (int i = 0; i <= str.length(); i++) {
                if (str[i] == delimiter || str[i] == '\0') {
                    result.push_back(str.substr(last, i - last));
                    last = i + 1;
                }
            }
            return result;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.