# Serialize Deserialize

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.

## Note

* **If given Tree is Binary Search Tree?**

  If the given Binary Tree is Binary Search Tree, we can store it by either storing preorder or postorder traversal. In case of Binary Search Trees, only preorder or postorder traversal is sufficient to store structure information.
* **If given Binary Tree is Complete Tree?**

  A Binary Tree is complete if all levels are completely filled except possibly the last level and all nodes of last level are as left as possible (Binary Heaps are complete Binary Tree). For a complete Binary Tree, level order traversal is sufficient to store the tree. We know that the first node is root, next two nodes are nodes of next level, next four nodes are nodes of 2nd level and so on.
* **If given Binary Tree is Full Tree?**

  A full Binary is a Binary Tree where every node has either 0 or 2 children. It is easy to serialize such trees as every internal node has 2 children. We can simply store preorder traversal and store a bit with every node to indicate whether the node is an internal node or a leaf node.
* **How to store a general Binary Tree?**

  A simple solution is to store both Inorder and Preorder traversals. This solution requires requires space twice the size of Binary Tree. We can save space by storing Preorder traversal and a marker for NULL pointers.

### 解决这题的关键就是，自己补位，构建一个 full binary tree 出来。 <a href="#jie-jue-zhe-ti-de-guan-jian-jiu-shi-zi-ji-bu-wei-gou-jian-yi-ge-fullbinarytree-chu-lai" id="jie-jue-zhe-ti-de-guan-jian-jiu-shi-zi-ji-bu-wei-gou-jian-yi-ge-fullbinarytree-chu-lai"></a>

## Option One - Preorder

```
We may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "1,2,#,#,3,4,#,#,5,#,#"
```

```java
public class Codec {
    private static final String NULL = "#";
    private static final String SEP = ",";

    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }

        StringBuilder sb = new StringBuilder();
        // PreOrder traversal
        Stack<TreeNode> s = new Stack<>();
        s.push(root);
        while (!s.isEmpty()) {
            TreeNode cur = s.pop();
            if (cur == null) {
                sb.append(NULL).append(SEP);
                continue;
            }
            sb.append(cur.val).append(SEP);
            s.push(cur.right);
            s.push(cur.left);
        }

        sb.setLength(sb.length() - 1);
        //System.out.print(sb.toString());
        return sb.toString();
    }

    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }

        StringTokenizer st = new StringTokenizer(data, SEP);
        return deseriaHelper(st);
    }

    private TreeNode deseriaHelper(StringTokenizer st) {
        if (!st.hasMoreTokens()) {
            return null;
        }

        String val = st.nextToken();
        if (val.equals(NULL)) {
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(val));
        root.left = deseriaHelper(st);
        root.right = deseriaHelper(st);

        return root;
    }
}
```

## Option Two - Level order

```
We may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "{1,2,3,#,#,4,5}"
```

```java
public class Codec {
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        sb.append("{");

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode curr = q.poll();
            if (curr == null) {
                sb.append("#");
            } else {
                q.offer(curr.left);
                q.offer(curr.right);
                sb.append(curr.val);
            }
            sb.append(",");
        }

        for (int i = sb.length() - 1; i >= 0; i--) {
            if (sb.charAt(i) == '#' || sb.charAt(i) == ',') {
                sb.deleteCharAt(i);
            } else {
                break;
            }
        }

        sb.append("}");
        System.out.print(sb.toString());
        return sb.toString(); 
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.equals("{}")) {
            return null;
        }

        String[] vals = data.substring(1, data.length() - 1).split(",");
        List<TreeNode> list = new ArrayList<>();
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        list.add(root);

        boolean flag = true;
        int index = 0;
        for (int i = 1; i < vals.length; i++) {
            if (!vals[i].equals("#")) {
                TreeNode node = new TreeNode(Integer.parseInt(vals[i]));
                if (flag) {
                    list.get(index).left = node;
                } else {
                    list.get(index).right = node;
                }
                list.add(node);
            }
            if (!flag) {
                index++;
            }
            flag = !flag;
        }

        return root;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://luj.gitbook.io/code/tree/7-serialize-and-deserialize/serializedeserialize.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.