297. Serialize and Deserialize Binary Tree

Link

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Example:

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]"

Clarification: The above format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Solution

Serialize

T: O(N), 就是針對每個node做 traversal

把所有null的節點填X(包含左右子樹本身)，然後node之間用","隔開，使用level Order traversals的方式去瑱入值。

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    if(root == null) return sb.toString();
    
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while(!queue.isEmpty()){
        TreeNode node = queue.poll();
        sb.append(node == null ? "x" : node.val);
        sb.append(",");
        if(node != null){
            queue.add(node.left);
            queue.add(node.right);
        }
    }
    return sb.toString();
    
}

Deserialize

T: O(N), 就是針對每個node做 還原

將input data根據","，切成若干個input data。

透過queue去紀錄下一個要填左右子樹的node 每次該node的左右子樹之後，把左右子樹加入queue中。

每次重複兩個input elelment。剛好對應此次要填入的左右子樹。

    public TreeNode deserialize(String data) {
        if(data.equals("")) return null;
        String[] nodes = data.trim().split(",");
        int n = nodes.length;
        if(n == 0) return null;
        int i = 1;
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();          
            node.left = nodes[i].equals("x") ? null : new TreeNode(Integer.parseInt(nodes[i]));
            i++;
            node.right = nodes[i].equals("x") ? null : new TreeNode(Integer.parseInt(nodes[i]));
            i++;
            if(i >= n) break;
            if(node.left != null) queue.add(node.left);
            if(node.right != null) queue.add(node.right);
        }
        return root;
        
    }