C++ Accepted O(n) Easy Solution


  • 16

    Idea: Level-order traversal. Use '#' to denote a nullptr. User ',' to separate entries. The output is very similar to Leetcode's default deserialization logic.

    --

    Time Complexities: O(n) to serialize and O(n) to deserialize

    Space Complexities: O(n) to serialize and O(n) to deserialize

    --

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Codec {
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            queue<TreeNode*> q;
            q.push(root);
            string str;
            while (!q.empty()) {
                if (q.front() == nullptr) {
                    str = str + "#,";
                } else {
                    q.push(q.front()->left);
                    q.push(q.front()->right);
                    str = str + to_string(q.front()->val) + ",";
                }
                q.pop();
            }
            return str;
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            TreeNode* root = nullptr;
            queue<TreeNode**> q;
            q.push(&root);
            string::iterator first = data.begin();
            while (first != data.end()) {
                TreeNode** pp = q.front();
                if (*first == '#') {
                    // *pp = nullptr;
                    advance(first, 2);
                } else {
                    string::iterator last = find(first, data.end(), ',');
                    int val = stoi(string(first, last));
                    *pp = new TreeNode(val);
                    q.push(&((*pp)->left));
                    q.push(&((*pp)->right));
                    first = next(last);
                }
                q.pop();
            }
            return root;
        }
    };
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec;
    // codec.deserialize(codec.serialize(root));

  • 0

    Nice implementation of the deserialize function using the double pointer. You can remove the line *pp = nullptr; because in the constructor of TreeNode it automatically initializes both of its children to null.


  • 0

    Yes, you are right! Thank you very much for your suggestion.


  • 0
    F

    Just out of curiosity, will leetcode oj take care of the memory you allocated in the deserialize function?


Log in to reply
 

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