297. Serialize and Deserialize Binary Tree

LeetCode

Both of our recursive and iterative solutions will add empty leaves for all the leaves in the original binary tree when running serialize. Even so, it won’t affect the deserialize result.

Recursive

In the recursive solution, we use a recursive preorder traversal-like method to implement serialize and use a recursive BFS-like method to implement deserialize.

/**
 * 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) {
        StringBuilder builder = new StringBuilder();
        serializeHelper(root, builder);
        return builder.toString();
    }

    private void serializeHelper(TreeNode root, StringBuilder builder) {
        if (root == null) {
            builder.append("n").append(",");
        } else {
            builder.append(root.val).append(",");
            serializeHelper(root.left, builder);
            serializeHelper(root.right, builder);
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] list = data.split(",");
        LinkedList<String> queue = new LinkedList<>(Arrays.asList(list));
        return deserializeHelper(queue);
    }

    private TreeNode deserializeHelper(LinkedList<String> queue) {
        String value = queue.removeFirst();
        if ("n".equals(value)) {
            return null;
        } else {
            TreeNode node = new TreeNode(Integer.parseInt(value));
            node.left = deserializeHelper(queue);
            node.right = deserializeHelper(queue);
            return node;
        }
    }
}

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

Iterative

In the recursive solution, we use a iterative BFS-like method to implement serialize and deserialize.

/**
 * 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) {
        final String separator = ",";
        final String nil = "n";
        StringBuilder builder = new StringBuilder();
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.removeFirst();
            if (node == null) {
                // representing null with a special string
                builder.append(nil).append(separator);
            } else {
                builder.append(node.val).append(separator);
                // we don't ignore empty leaves
                queue.addLast(node.left);
                queue.addLast(node.right);
            }
        }
        return builder.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        final String separator = ",";
        final String nil = "n";

        // corner case: empty tree
        if ((nil + separator).equals(data)) {
            return null;
        }

        String[] values = data.split(separator);
        LinkedList<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        queue.add(root);
        for (int i = 1; i < values.length - 1; i++) {
            TreeNode node = queue.removeFirst();
            String leftValue = values[i];
            String rightValue = values[++i];
            if (!leftValue.equals(nil)) {
                node.left = new TreeNode(Integer.parseInt(leftValue));
                queue.addLast(node.left);
            }
            if (!rightValue.equals(nil)) {
                node.right = new TreeNode(Integer.parseInt(rightValue));
                queue.addLast(node.right);
            }
        }
        return root;
    }
}

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