A 48 ms rough C++ solution, used queue.


  • 0

    I have followed LeetCode's style (which I think is quite easy to build a tree). Use 'x' to represent null.

    class Codec {
    public:
    
    	// Encodes a tree to a single string.
    	string serialize(TreeNode* root) 
    	{
    		if (!root)
    			return "";
    		queue<TreeNode*> q;
    		q.push(root);
    		string data;
    		data += to_string(root->val) + ',';
    		q.push(0);
    		while (!q.empty())
    		{
    			TreeNode *t = q.front();
    			q.pop();
    			if (t)
    			{
    				if (t->left)
    				{
    					q.push(t->left);
    					data += to_string(t->left->val) + ",";
    				}
    				else
    					data += "x,";
    				if (t->right)
    				{
    					q.push(t->right);
    					data += to_string(t->right->val) + ",";
    				}
    				else
    					data += "x,";
    			}
    			else if (!q.empty())
    				q.push(0);
    		}
    		return data;
    	}
    
    	// Decodes your encoded data to tree.
    	TreeNode* deserialize(string data) 
    	{
    		if (data.empty())
    			return 0;
    		int sz = data.size();
    		TreeNode *root = new TreeNode(0);
    		int pre, fol;
    		pre = fol = 0;
    		for (; ',' != data[pre]; ++pre);
    		string st = data.substr(fol, pre - fol);
    		root->val = stoi(st);
    		++pre;
    		fol = pre;
    		queue<TreeNode*> q;
    		q.push(root);
    		while (pre < sz && !q.empty())
    		{
    			TreeNode *t = q.front();
    			q.pop();
    			for (; pre < sz && ',' != data[pre]; ++pre);
    			st = data.substr(fol, pre - fol); 
    			++pre;
    			fol = pre;
    			if ("x" != st)
    			{
    				TreeNode* le = new TreeNode(stoi(st));
    				t->left = le;
    				q.push(le);
    			}
    			for (; pre < sz && ',' != data[pre]; ++pre);
    			st = data.substr(fol, pre - fol);
    			++pre;
    			fol = pre;
    			if ("x" != st)
    			{
    				TreeNode* ri = new TreeNode(stoi(st));
    				t->right = ri;
    				q.push(ri);
    			}
    		}
    		return root;
    	}
    };

Log in to reply
 

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