297 Serialize and Deserialize Binary Tree

BFS

這題主要是要考資料結構的serialization

• idea:

  • serialize: bfs visit all nodex, and concate to a string. use node_count to count total number of non null nodes
  • deserialize: read data and split by ',' create the first node and put it into queue read other nodes, link them to their parents in order, then put into queue too while loop ends when idx > splitData.length

• code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        /*
        bfs visit all nodes.
        and concate to a string
        */
        String s = "";
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int count_node = 1;
        while(!queue.isEmpty() && count_node > 0){
            TreeNode cur = queue.poll();
            if(cur!=null){
                s += cur.val + ",";
                count_node--;
            }
            else    s += "null,";
            if(cur != null){
                if(cur.left != null){
                    queue.offer(cur.left);
                    count_node++;
                }
                else    queue.offer(null);

                if(cur.right != null){
                    queue.offer(cur.right);
                    count_node++;
                }
                else    queue.offer(null);
            }
        }

        return s.substring(0,s.length()-1);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        /*
            read data and split by ','
            create the first node and put it into queue
            read other nodes, link them to their parents in order, then put into queue too
        */
        //base check
        if(data.length()== 0 || data.equals("") || data.equals("null")){
            return null;
        }

        //split
        String[] splitData = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(splitData[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int idx = 1;//for splitData count

        while(!queue.isEmpty() && idx < splitData.length){
            TreeNode cur = queue.poll();
            String leftidx = splitData[idx++];
            String rightidx = "";
            if(idx < splitData.length)
                rightidx = splitData[idx++];

            TreeNode left=null, right=null;
            if(!leftidx.equals("null") && !leftidx.equals("")){
                left = new TreeNode(Integer.parseInt(leftidx));
                cur.left = left;
                queue.offer(left);
            }
            if(!rightidx.equals("null") && !rightidx.equals("")){
                right = new TreeNode(Integer.parseInt(rightidx));
                cur.right = right;
                queue.offer(right);
            }
        }

        return root;
    }
}

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

這個做法速度頗慢，雖然能AC，但只贏過2%

Recursive

我們也可以不要用BFS的作法，直接用recursive的解法，只是要先把serialize跟deserialize的順序想好，再來實作程式碼。

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == NULL) return "#";
        return to_string(root->val) + "," + serialize(root->left) + "," + serialize(root->right);
    }

    TreeNode* deserialize(string data) {
        if (data == "#") return NULL;
        stringstream s(data);
        return makeDeserialize(s);
    }

    TreeNode* makeDeserialize(stringstream& s) {
        string str;
        getline(s, str, ',');
        if (str == "#") {
            return NULL;
        } else {
            TreeNode* root = new TreeNode(stoi(str));
            root->left = makeDeserialize(s);
            root->right = makeDeserialize(s);
            return root;
        }
    }
};

其中stringstream的部分在使用getline之後，會自動把已經取出的部分砍掉。寫一小段程式碼來驗證這個行為:

#include <iostream>
#include <sstream>
using namespace std;

int main() {
    // your code goes here
    stringstream ss("1,2,3,4,5,6");

    string str;

    getline(ss, str, ',');
    cout << str << endl;

    getline(ss, str, ',');
    cout << str << endl;

    return 0;
}

以上這段程式碼執行的結果就是:

1
2