Easy and clean BFS based C++ 26ms solution, beating 95%


  • 0
    C

    The schema used here is BFS order or level order, for each node in tree we record their left and right children. So when we deserialize, we just need to use the BFS traversal again and for current level nodes, read two from the buffer and assign to left and right.

    To save memory, I used binary format of the tree, the total memory used here is around 6 * n bytes worst case.

    Here's how we encode.

    We use 4 byte to encode the int value of TreeNode. And since BFS order requires us to include empty child nodes of real nodes in the binary tree, and we can use 1 byte to encode NULL nodes.
    To differentiate normal TreeNode with NULL, we use an sentinel bit to differentiate them.

    So we are using:
    1 byte + 4 byte for actual nodes
    1 byte for NULL child of those actual nodes.

    Let N be the number of nodes in the tree, there could be maximum of N NULL children, so the worst case space we use is actually 6N bytes, compared with 8N bytes if we use inorder + preorder/postorder scheme.

    Code:

    class Codec {
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            queue<TreeNode*> current;
            string buffer;
            if (root) {
                current.push(root);
                writeOne(buffer, root);
            }
            
            while (!current.empty()) {
                int size = current.size();
                for (int i=0; i<size; i++) {
                    TreeNode* node = current.front();
                    current.pop();
                    writeOne(buffer, node->left);
                    writeOne(buffer, node->right);
                    if (node->left) current.push(node->left);
                    if (node->right) current.push(node->right);
                }
            }
    
            return buffer;
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            if (data.empty()) return NULL;
            const char* buffer = data.c_str();
            TreeNode* root = readOne(buffer);
            queue<TreeNode*> current;
            if (root) current.push(root);
            
            while (!current.empty()) {
                int size = current.size();
                for (int i=0; i<size; i++) {
                    TreeNode* node = current.front();
                    current.pop();
                    node->left = readOne(buffer);
                    node->right = readOne(buffer);
                    if (node->left) current.push(node->left);
                    if (node->right) current.push(node->right);
                }
            }
            
            return root;
        }
        
        inline void writeOne(string& buffer, TreeNode* node) {
            if (node) {
                buffer += '1';
                char tmp[4];
                memcpy(tmp, &(node->val), sizeof(int));
                for (int i=0; i<4; i++) buffer += tmp[i];
            } else {
                buffer += '0';
            }
        }
        
        inline TreeNode* readOne(const char*& buffer) {
            if (!buffer || *buffer == '\0') return NULL;
            if (*buffer == '1') {
                buffer++;
                int value;
                memcpy(&value, buffer, sizeof(int));
                buffer += sizeof(int);
                return new TreeNode(value);
            } else {
                buffer++;
                return NULL;
            }
        }
    };
    

Log in to reply
 

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