# Serialize and Deserialize Binary Tree

<https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/>

> 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.

## Thoughts

这道题开始想用传统的数组存储法做，即中间结点是root, 左边的是左子树，右边的是右子树。但它的缺点很明显，一来代码写的长，二来所需空间多（即使只存所在位置也无济于事），三来算中点时可能越界。

后来看到高手写的用preorder serialize 和同样调用preorder deserialize, 值得学习。

dfs顺着最左一路捅到底(遇到NULL), backtracking(回栈顶)换边, 继续捅

node/cur是当前, subs\[i]是要被插入的, 遇到NULL停止继续搜索.

deserilize当前点和subs\[i]的关系:

1. dfs recursive node即subs\[i], node左子树是subs\[i+1, ..] 直到遇到NULL, backtracking 紧接着是右子树.
2. iterative: 当subs\[i]不为null, 一直往左下插, 当遇到null意味着要backtracking换边
3. bfs i和i+1一定是node的左和右.&#x20;

## Code

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    private final String SPLITER = "/";
    private final String NULL = "#";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if (root == null) {
            sb.append(NULL).append(SPLITER);
        } else {
            sb.append(root.val).append(SPLITER);
            sb.append(serialize(root.left));
            sb.append(serialize(root.right));
        }
        return sb.toString();
    }

    int i = -1;
    private TreeNode dfs(String[] subs) {
        i++;
        if (subs[i].equals(NULL)) {
            return null;
        }
        TreeNode node = new TreeNode(Integer.parseInt(subs[i]));
        node.left = dfs(subs);
        node.right = dfs(subs);
        return node;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] subs = data.split(SPLITER);
        return dfs(subs);
    }
}

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

## Analysis

时间复杂度O(n), 空间复杂度O(n).

## Ver.2

栈内存当前的path, iterative解法的难点在于知道什么时候该backtracing和backtracing到哪里.\
由于是二叉树, 有个比较巧妙的解法, 类似在树上做traversal, 维持cur和stack (当前path). 在树上做时是当cur为null时, 让栈顶及父节点帮助改变遍历方向. 这里是用cur来帮助转方向, 让stack只要遇到NULL就pop, 当连遇到两个NULL时意味是叶子, stack中把叶子和它的父节点都pop出来, cur指向父节点. 还有当进入右子节点时, 上一个访问的一定是NULL.

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    private final String SPLITER = "/";
    private final String NULL = "#";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node == null) {
                sb.append(NULL);
            } else {
                sb.append(node.val);
                stack.push(node.right);
                stack.push(node.left);
            }
            sb.append(SPLITER);
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] subs = data.split(SPLITER);
        if (subs[0].equals(NULL)) {
            return null;
        }
        //System.out.println(data);
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = new TreeNode(Integer.parseInt(subs[0]));
        TreeNode cur = root;
        stack.push(root);
        for (int i = 1; i < subs.length; i++) {
            if (!subs[i].equals(NULL)) {  
                TreeNode node = new TreeNode(Integer.parseInt(subs[i]));
                if (subs[i - 1].equals(NULL)) {
                    cur.right = node;
                    cur = cur.right;
                    stack.push(cur);
                } else {
                    cur.left = node;
                    cur = cur.left;
                    stack.push(cur);
                }
            } else if (!stack.isEmpty()) {
                cur = stack.pop();
            }
        }

        return root;
    }
}

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

## Ver.3

当是k叉树(k已知)时, 就不能遇到NULL就pop了. 栈依然是path, 栈顶是当前节点. 我们可以用一个map做计数器, 记录每个节点已经访问过了几个边.\
当所有边都已经访问过时, pop/backtracing. 由于可能出现连续pop/backtracking的情况, 用一个循环连续检查栈顶.

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    private final String SPLITER = "/";
    private final String NULL = "#";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (node == null) {
                sb.append(NULL);
            } else {
                sb.append(node.val);
                stack.push(node.right);
                stack.push(node.left);
            }
            sb.append(SPLITER);
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] subs = data.split(SPLITER);
        if (subs[0].equals(NULL)) {
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> meta = new Stack<>();
        TreeNode root = new TreeNode(Integer.parseInt(subs[0]));
        Map<TreeNode, Integer> map = new HashMap<>();
        stack.push(root);
        for (int i = 1; i < subs.length; i++) {
            while (!stack.isEmpty() && map.containsKey(stack.peek()) && map.get(stack.peek()) == 2) {
                stack.pop();
            }
            TreeNode cur = stack.peek();
            if (!subs[i].equals(NULL)) {  
                TreeNode node = new TreeNode(Integer.parseInt(subs[i]));
                if (map.containsKey(cur) && map.get(cur) == 1) {
                    cur.right = node;
                    stack.push(node);
                } else {
                    cur.left = node;
                    stack.push(node);
                }
            }
            map.put(cur, map.getOrDefault(cur, 0) + 1);
        }

        return root;
    }
}

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

## Ver. 4

BFS

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    private final String SPLITER = "/";
    private final String NULL = "#";

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

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] subs = data.split(SPLITER);
        if (subs[0].equals(NULL)) {
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(subs[0]));
        queue.offer(root);
        int i = 1;
        while (i < subs.length) {
            TreeNode node = queue.poll();
            if (!subs[i].equals(NULL)) {
                node.left = new TreeNode(Integer.parseInt(subs[i]));
                queue.offer(node.left);
            }
            i++;
            if (!subs[i].equals(NULL)) {
                node.right = new TreeNode(Integer.parseInt(subs[i]));
                queue.offer(node.right);
            }
            i++;
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(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://hao-fu-1.gitbook.io/oj/binary_tree_and_divide_conquer/order-traversal/serialize-and-deserialize-binary-tree.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.