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的左和右.

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));