C++ preorder and using ( ) for help


  • 0
    J
    /**
     * 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) {
            return preorder(root);
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            if(data.size()==0) return NULL;
            int i = 0;
            while(i<data.size() && data[i]!='(')i++;
            string root_str = data.substr(0,i);
            stack<char> stk;
            stk.push('(');
            int idx1 = i;
            i++;//skip the '('
            while(!stk.empty()&&i<data.size())
            {
                if(data[i]=='(') stk.push(data[i]);
                if(data[i]==')') stk.pop();
                i++;
            }
            string left = data.substr(idx1+1,i-idx1-2);//注意这里的index
            string right = data.substr(i+1,data.size()-i-2);
            TreeNode *root = new TreeNode(stoll(root_str));
            root->left = deserialize(left);
            root->right = deserialize(right);
            return root;
            
        }
        
        string preorder(TreeNode*root)
        {
            if(!root) return "";
            return to_string(root->val) + "("+preorder(root->left)+")"+"("+preorder(root->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.