C++ solution which produces most compact encoded string


  • 0
    A

    Serialize by preorder traverse. Deserialize by building the BST from elements one by one.

    class Codec {
    public:
        void helperS(string &ans, TreeNode *root) {
            if (!root)
                return;
            
            ans += (ans.empty() ? "" : ",") + to_string(root->val);
            helperS(ans, root->left);
            helperS(ans, root->right);
        }
        
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            string ans;
            helperS(ans, root);
            return ans;
        }
        
        void build(TreeNode *&node, int num) {
            if (!node)
                node = new TreeNode(num);
            else
                build(num < node->val ? node->left : node->right, num);
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            stringstream ss(data);
            vector<int> nums;
            string s;
            while (!ss.eof()) {
                getline(ss, s, ',');
                if (!s.empty())
                    nums.push_back(stoi(s));
            }
            
            TreeNode *root = NULL;
            for (int num : nums)
                build(root, num);
            return root;
        }
    };
    

Log in to reply
 

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