C++ Stack-based Iterative Solution (Use Only one character between any nodes)


  • 0
    W
    class Codec {
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            ostringstream os;
            serialHelper(root, os);
            string rt = os.str();
            if(!rt.empty()) rt.pop_back();
            return rt;
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            if(data.empty()) return NULL;
            istringstream is(data);
            string str;
            TreeNode* root;
            stack<TreeNode*> stk;
            while(getline(is, str, ' ')) {
                int num = stoi(str);
                TreeNode* newnode = new TreeNode(num);
                TreeNode* prev = NULL;
                while(!stk.empty() && stk.top()->val < num) {
                    prev = stk.top();
                    stk.pop();
                }
                if(prev != NULL) {
                    prev->right = newnode;
                    stk.push(newnode);
                }
                else {
                    if(stk.empty()) root = newnode;
                    else stk.top()->left = newnode;
                    stk.push(newnode);
                }
            }
            return root;
        }
        
    private:
        void serialHelper(TreeNode* root, ostringstream& os) {
            if(root == NULL) return;
            os << root->val << ' ';
            serialHelper(root->left, os);
            serialHelper(root->right, os);
        }
    };
    

Log in to reply
 

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