Simple C++ iterative solution


  • 0
    G
    /**
     * 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:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) {
            //preorder traversal with stack
            string ans;
            stack<TreeNode*> st;
            st.push(root);
            while(st.size()){
                auto nd = st.top();
                st.pop();
                if(!nd) ans += "#,";
                else{
                    ans += to_string(nd->val) + ",";
                    st.push(nd->right);
                    st.push(nd->left);
                }
            }
            return ans;
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            //get string tokens
            int i = 0;
            vector<string> token;
            while(i < data.size()){
                int next = data.find(',', i);
                token.push_back(data.substr(i, next - i));
                i = next + 1;
            }
            //inorder traversal with stack
            stack<TreeNode*> st;
            i = -1;
            auto extra = new TreeNode(0);
            st.push(extra);
            while(st.size()){
                auto nd = st.top();
                st.pop();
                if(token[++i] != "#"){
                    st.push(nd = nd->right = new TreeNode(stoi(token[i])));
                    while(token[++i] != "#")
                        st.push(nd = nd->left = new TreeNode(stoi(token[i])));
                }
            }
            return extra->right;
        }
    };
    
    // 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.