Preorder, such as creating bt method


  • 3
    R
    /**
     * 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) {
            string encode;
            dfs(root, encode);
            return encode;
        }
        void dfs(TreeNode* root, string& encode){
            if(!root){
                encode+="*,";
                return ;
            }
            encode+=to_string(root->val)+",";
            dfs(root->left, encode);
            dfs(root->right, encode);
        }
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            int i = 0;
            TreeNode* root;
            Create(root, i, data);
            return root;
        }
        void Create(TreeNode*& root, int& i, string& data){
            if(data[i]=='*'){
                root=NULL;
                i+=2;
            }
            else{
                int num=0;
                bool flag=0;
                if(data[i]=='-'){
                    flag=1;
                    i++;
                }else if(data[i]=='+'){
                    i++;
                }
                while(i<data.size() && isdigit(data[i])) num=num*10+data[i]-'0', i++;
                i++;
                root=new TreeNode(!flag ? num : -num);
                Create(root->left, i, data);
                Create(root->right, i, data);
            }
        }
    };
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec;
    // codec.deserialize(codec.serialize(root));
    

    similar to LC serialize BT, level order, code easy but long, I think it need at least 20 minutes for coding.

    /**
     * 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) {
            string ans;
            queue<TreeNode*> q;
            if(!root){
                ans+="*,";
            }else{
                ans+=to_string(root->val)+",";
                q.push(root);
            }
            while(!q.empty()){
                auto cur = q.front(); q.pop();
                if(cur->left){
                    ans+=to_string(cur->left->val)+",";
                    q.push(cur->left);
                }else{
                    ans+="*,";
                }
                if(cur->right){
                    ans+=to_string(cur->right->val)+",";
                    q.push(cur->right);
                }else{
                    ans+="*,";
                }
            }
            return ans;
        }
        int extract(string data, int& i){
            bool flag=0;
            if(data[i]=='-'){
                flag=1;
                i++;
            }else if(data[i]=='+'){
                i++;
            }
            int num=0;
            while(i<data.size() && isdigit(data[i])) num=num*10+data[i]-'0', i++;
            i++;
            return !flag ? num : -num;
        }
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) {
            int i=0;
            queue<TreeNode*> q;
            TreeNode* root;
            if(data[i]=='*'){
                root=NULL;
                i+=2;
            }else{
                int num = extract(data, i);
                root=new TreeNode(num);
                q.push(root);
            }
            while(!q.empty()){
                auto cur = q.front(); q.pop();
                if(data[i]=='*'){
                    cur->left=NULL;
                    i+=2;
                }else{
                    int num= extract(data, i);
                    cur->left=new TreeNode(num);
                    q.push(cur->left);
                }
                if(data[i]=='*'){
                    cur->right=NULL;
                    i+=2;
                }else{
                    int num= extract(data, i);
                    cur->right=new TreeNode(num);
                    q.push(cur->right);
                }
            }
            return root;
        }
    };
    
    // 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.