Recursive, preorder traversal, little endian C++ solution.


  • 1
    S
    /**
     * 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:
        int decodeInt(string &s, int begin){
            int v = 0;
            for(int i = 0; i < 4; i++){
                int t = s[i + begin];
                v |= ((t & 0xff) << (i << 3));
            }
            return v;
        }
        
        string encodeInt(int v){
            string s;
            for(int i = 0; i < 4; i++){
                s.push_back(v & 0xff);
                v >>= 8;
            }
            return s;
        }
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            return encodeDFS(root);
        }
        
        string encodeDFS(TreeNode *node){
            if(!node) return string();
            return encodeInt(node->val) + encodeDFS(node->left) + encodeDFS(node->right);
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            //cout<<data<<endl;
            return deserializeHelper(data, 0, data.length());
        }
        
        TreeNode* deserializeHelper(string &data, int left, int right){
            if(left == right) return nullptr;
            int v = decodeInt(data, left);
            //cout<<v<<endl;
            TreeNode *node = new TreeNode(v);
            int mid = right;
            for(int i = left + 4; i < right; i += 4){
                int t = decodeInt(data, i);
                if(t > v) {
                    mid = i;
                    break;
                }
            }
            node->left = deserializeHelper(data, left + 4, mid);
            node->right = deserializeHelper(data, mid, right);
            return node;
        }
    };
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec;
    // codec.deserialize(codec.serialize(root));
    

Log in to reply
 

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