[C++] Clean Code - Iterative/Recursive - "((1)2(3))"


  • 0

    Iterative

    class Codec {
    public:
        string serialize(TreeNode* root) {
            return !root ? "" : "(" + serialize(root->left) + to_string(root->val) + serialize(root->right) + ")";
        }
    
        TreeNode* deserialize(string data) {
            TreeNode* node = nullptr;
            stack<TreeNode*> s;
            for (int i = 0; i + 1 < data.length(); i++) {   // here we check i+1 < data.length() to skip the last ')'
                if (data[i] == '-' || isdigit(data[i])) {
                    int start = i;
                    while (i + 1 < data.length() && isdigit(data[i + 1])) { i++; }
                    node->val = stoi(data.substr(start, i + 1 - start));
                }
                else if (data[i] == '(') {
                    s.push(node);
                    node = new TreeNode(INT_MIN); // INT_MIN as uninitialized node value
                }
                else if (data[i] == ')') {
                    s.top()->val == INT_MIN ? s.top()->left = node : s.top()->right = node;
                    node = s.top();
                    s.pop();
                }
            }
            return node;
        }
    };
    

    Recursive

    class Codec {
    public:
        string serialize(TreeNode* root) {
            return !root ? "" : "(" + serialize(root->left) + to_string(root->val) + serialize(root->right) + ")";
        }
    
        TreeNode* deserialize(string data) {
            int i = 0;
            return parse(data, i);
        }
    private:
        TreeNode* parse(string& s, int& i) {
            if (s[i] != '(') {
                return nullptr;
            }
            TreeNode* node = new TreeNode(INT_MIN);
            i++;    // skip '('
            node->left = parse(s, i);
            if (s[i] == '-' || isdigit(s[i])) {
                int start = i++;
                while (i < s.size() && isdigit(s[i])) { i++; }
                node->val = stoi(s.substr(start, i - start));
            }
            node->right = parse(s, i);
            i++;    // skip ')'
            return node;
        }
    };
    

Log in to reply
 

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