C++ BFS iterative, no fancy stuff.


  • 0
    A
     class Codec {
     public:
    
    	 // Encodes a tree to a single string.
    	 string serialize(TreeNode* root) {
    		 string returnValue;
    		 if (!root)
    			 return returnValue;
    		 vector<TreeNode*> currentLevel;
    		 currentLevel.push_back(root);
    		 while (!currentLevel.empty()) {
    			 vector<TreeNode*> nextLevel;
    			 for(TreeNode * i : currentLevel) {
    				 if (i != NULL) {
    					 ostringstream oss;
    					 oss << i->val;
    					 returnValue += (oss.str() + ",");
    					 nextLevel.push_back(i->left);
    					 nextLevel.push_back(i->right);
    				 }
    				 else {
    					 returnValue += "#,";
    				 }
    			 }
    			 currentLevel = nextLevel;
    		 }
    		 return returnValue;
    	 }
    
    	 // Decodes your encoded data to tree.
    	 TreeNode* deserialize(string data) {
    		 if (data.empty())
    			 return NULL;
    		 vector<TreeNode*> previousLevel;
    		 TreeNode * newNode = new TreeNode(stoi(data.substr(0, data.find(","))));
    		 previousLevel.push_back(newNode);
    		 data.erase(0, data.find(",") + 1);
    		 while (!data.empty()) {
    			 vector<TreeNode*> currentLevel;
    			 for(int j = 1; j <=2 * previousLevel.size(); ++ j) {
    				string value = data.substr(0, data.find(","));
    				data.erase(0, data.find(",") + 1);
    				if (value != "#") {
    					TreeNode * newNode = new TreeNode(stoi(value));
    					if (j % 2)
    						previousLevel[(j-1)/2]->left = newNode;
    					else
    						previousLevel[(j-1)/2]->right = newNode;
    					currentLevel.push_back(newNode);
    				}
    			 }
    			 previousLevel = currentLevel;
    		 }
    		 return newNode;
    	 }
     };
    // 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.