Easy To Understand C++ Solution Using PreOrder Traversal and iostringstream


  • 2

    Because of BST, so we can use PreOrder Traversal to rebuild the tree, so do with serialize and deserialize. After using iostringstream, we can easily get the values and build the tree.

    class Codec 
    {
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) 
        {
            ostringstream out;
            mySerialize(root, out);
            return out.str();
        }
    
        // Decodes your encoded data to tree.
        TreeNode* deserialize(string data) 
        {
            if(data == "") return NULL;
            istringstream in(data);
            return myDeserialize(in);
        }
    private:
    	void mySerialize(TreeNode* root, ostringstream &out)
    	{
    		if(root == NULL) return;
    		out << root->val << " ";
    		mySerialize(root->left, out);
    		mySerialize(root->right, out);
    	}
    
    	TreeNode* myDeserialize(istringstream &in)
    	{
    		string val;
    		in >> val;
    		TreeNode *root = new TreeNode(stoi(val));
    		while(in >> val)
    			buildTree(root, stoi(val));
    		return root;
    	}
    
    	void buildTree(TreeNode* root, int n)
    	{
    		if(root->val > n)
    		{
    			if(root->left == NULL)
    				root->left = new TreeNode(n);
    			else
    				buildTree(root->left, n);
    		}
    		else
    		{
    			if(root->right == NULL)
    				root->right = new TreeNode(n);
    			else
    				buildTree(root->right, n);
    		}
    	}
    };
    

  • 0
    S

    @贫贫贫贫僧 said in Easy To Understand C++ Solution Using PreOrder Traversal and iostringstream:

    class Codec
    {
    public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) 
    {
        ostringstream out;
        mySerialize(root, out);
        return out.str();
    }
    
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) 
    {
        if(data == "") return NULL;
        istringstream in(data);
        return myDeserialize(in);
    }
    

    private:
    void mySerialize(TreeNode* root, ostringstream &out)
    {
    if(root == NULL) return;
    out << root->val << " ";
    mySerialize(root->left, out);
    mySerialize(root->right, out);
    }

    TreeNode* myDeserialize(istringstream &in)
    {
    string val;
    in >> val;
    TreeNode *root = new TreeNode(stoi(val));
    while(in >> val)
    buildTree(root, stoi(val));
    return root;
    }

    void buildTree(TreeNode* root, int n)
    {
    if(root->val > n)
    {
    if(root->left == NULL)
    root->left = new TreeNode(n);
    else
    buildTree(root->left, n);
    }
    else
    {
    if(root->right == NULL)
    root->right = new TreeNode(n);
    else
    buildTree(root->right, n);
    }
    }
    };

    This is a great solution:

    1. It doesn't use a "#" to denote null node, which meet the requirement that we want the serialized string as compact as possible,
    2. It process the node one by one simply using property of BST. Most people use search to find the start and end of left child and right child, it is erroneous.

Log in to reply
 

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