c++ solution by queue


  • 0
    W

    /**

    • 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) {
      if(root==NULL)return "";
      string re="";
      deque<TreeNode*>qu;
      qu.push_back(root);
      re+=itoa(root->val);
      while(!qu.empty())
      {
      TreeNode*t=qu.front();
      qu.pop_front();
      if(t->left==NULL)re+=",null";
      else{
      re+=",";
      re+=itoa(t->left->val);
      qu.push_back(t->left);
      }
      if(t->right==NULL)re+=",null";
      else{
      re+=",";
      re+=itoa(t->right->val);
      qu.push_back(t->right);
      }
      }
      return re;

    }
    
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        vector<string>str;
        split(data,str);
        int len=str.size();
        if(len==0)return NULL;
        deque<TreeNode*>qu;
        TreeNode* root=new TreeNode(atoi(str[0]));
        qu.push_back(root);
        int i=0;
        while(!qu.empty())
        {
            TreeNode* t=qu.front();
            qu.pop_front();
            if(++i<len&&str[i]!="null")
            {
                TreeNode* l=new TreeNode(atoi(str[i]));
                t->left=l;
                qu.push_back(l);
                
            }
            else t->left=NULL;
            if(++i<len&&str[i]!="null")
            {
                TreeNode* r=new TreeNode(atoi(str[i]));
                t->right=r;
                qu.push_back(r);
            }
           else t->right=NULL;
            
        }
        return root;
        
        
        
    }
    
    void split(const string& data,vector<string>& str)
    {
        str.clear();
        int len=data.length();
        string temp="";
        for(int i=0;i<len;i++)
        {
            if(data[i]==',')
                {str.push_back(temp);temp="";}
            else
            temp+=data[i];
            
        }
        if(temp!="")str.push_back(temp);
    }
    int atoi(string s)
    {
        int sum=0,len=s.size();
        for(int i=0;i<len;i++)
        {
            sum=sum*10+s[i]-'0';
        }
        return sum;
    }
    string itoa(int num)
    {
        string re="";
        while(num!=0)
        {
            int t=num%10;
            re+=(t+'0');
            num/=10;
        }
        int len=re.size();
        for(int i=0;i<len/2;i++)
        {
            swap(re[i],re[len-1-i]);
        }
        return re;
    }
    //TreeNode* tree;
    

    };

    // Your Codec object will be instantiated and called as such:
    // Codec codec;
    // codec.deserialize(codec.serialize(root));


  • 0
    G

    great answer


Log in to reply
 

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