Binary Tree Serialization

Design an algorithm and write code to serialize and deserialize a binary tree. Writing the tree to a file is called 'serialization' and reading back from the file to reconstruct the exact same binary tree is 'deserialization'.

http://www.lintcode.com/en/problem/binary-tree-serialization/

Discussion

serialize 输出一个string很简单，preorder就可以了，空的位置输出”#“。关键是怎么根据string deserialize，具体是怎么提取出来string里面的number，用istringstream完美解决。

Solution

//O(n) run time
//O(n) space
class Solution {
public:
    /**
     * This method will be invoked first, you should design your own algorithm 
     * to serialize a binary tree which denote by a root node to a string which
     * can be easily deserialized by your own "deserialize" method later.
     */
    string serialize(TreeNode *root) {
        // write your code here
        string result;
        serializeHelper(root, result);
        return result;
    }

    /**
     * This method will be invoked second, the argument data is what exactly
     * you serialized at method "serialize", that means the data is not given by
     * system, it's given by your own serialize method. So the format of data is
     * designed by yourself, and deserialize it here as you serialize it in 
     * "serialize" method.
     */
    TreeNode *deserialize(string data) {
        // write your code here
        istringstream in(data); //O(n) space
        return deserializeHelper(in);
    }
private:
    void serializeHelper(TreeNode *root, string &output) {
        if(root == NULL) {
            output.append("# ");
        } else {
            output.append(to_string(root->val) + " ");
            serializeHelper(root->left, output);
            serializeHelper(root->right, output);
        }
    }
    TreeNode* deserializeHelper(istringstream &in) {
        string val;
        in >> val;
        if(val == "#") {
            return NULL;
        }
        TreeNode *node = new TreeNode(stoi(val));
        node->left = deserializeHelper(in);
        node->right = deserializeHelper(in);
        return node;
    }
};

Follow up

上面的serialize是tail recursion，转换成iteration比较容易。

string serialize(TreeNode *root) {
        // write your code here
        ostringstream output;
        stack<TreeNode*> stk;
        stk.push(root);
        while(stk.empty() == false) {
            TreeNode *cur  = stk.top();
            stk.pop();
            if(!cur) {
                output << "# ";
            } else {
                output << cur->val <<" ";
                stk.push(cur->right);
                stk.push(cur->left);
            }
        }
        return output.str();
    }

deserialize还没想好怎么转换。

先吧deserize函数写成tail recursion的形式，不用返回参数了。

TreeNode *deserialize(string data) {
        // write your code here
        istringstream in(data);
        TreeNode *root=NULL;
        deserializeHelper(in, root);
        return root;
    }
private:
    void deserializeHelper(istringstream &in, TreeNode *&node) {//指针引用
        string val;
        in >> val;
        if(val == "#") {
            return;
        }
        node = new TreeNode(stoi(val));
        deserializeHelper(in, node->left);
        deserializeHelper(in, node->right);
        //return node;
    }

Iteration method.

    TreeNode *deserialize(string data) {
        // write your code here
        if (data.length() == 0) return NULL;
        istringstream in(data);
        TreeNode *root=NULL;
        string val;
        in >> val;
        if(val == "#") {
            return root;
        }
        root = new TreeNode(stoi(val));
        stack<TreeNode**> stk;//看上文的recursion版本中传递的是指针引用
        stk.push(&root);
        stk.push(&(root->right)); 
        stk.push(&(root->left));
        while(in >> val) {
            TreeNode **cur = stk.top();
            stk.pop();
            if(val == "#") {
                *cur = NULL;
            } else {
                *cur = new TreeNode(stoi(val));
                stk.push(&((*cur)->right));
                stk.push(&((*cur)->left));
            }
        }

        return root;
    }

Reference

• Serialize and Deserialize a Binary Tree