Not Very Concise, But One Pass C++ Solution


  • 0
    class Codec {
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            if (!root) return "";
            return to_string(root->val) + " " + serialize(root->left) + " " +  serialize(root->right);
        }
    
        // Decodes your encoded data to tree.
        TreeNode* help(stringstream& s, TreeNode* par, int upperbound) {
            string str;
            auto it = s.tellg();
            s >> str;
            if (s.eof()) return nullptr;
            int val = stoi(str);
            if (val > upperbound) {
                s.seekg(it, s.beg);
                return nullptr;
            }
            TreeNode* p = new TreeNode(val);
            p->left = p->right = nullptr;
            if (val > par->val) {
                par->right = p;
                help(s, p, upperbound);
            }
            else {
                par->left = p;
                help(s, p, par->val);
                help(s, par, upperbound);
            }
            return p;
        }
        
        TreeNode* deserialize(string data) {
            stringstream s(data);
            TreeNode* dummy = new TreeNode(INT_MAX);
            return help(s, dummy, INT_MAX);
        }
    };
    

Log in to reply
 

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