Question

Formatted question description: https://leetcode.ca/all/297.html

 297	Serialize and Deserialize Binary Tree

 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.

 @tag-tree
 @Grammarly

Algorithm

Pre-order.

For serialization, we start from the root node. If the node exists, store the value in the output string stream, and then recursively call the serialization function on its left and right child nodes.

For deserialization, we first read in the first character to generate a root node, and then recursively call the deserialization function on the left and right child nodes of the root node.

Code

Java

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Serialize_and_Deserialize_Binary_Tree {

    public static void main(String[] args) {
        Serialize_and_Deserialize_Binary_Tree out = new Serialize_and_Deserialize_Binary_Tree();
        Codec_bfs s = out.new Codec_bfs();

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(5);

//        System.out.println(s.serialize(root)); // 1,2,X,X,3,4,X,X,5,X,X,
//
//        System.out.println(s.deserialize("1,2,X,X,3,4,X,X,5,X,X,").val);

        System.out.println(s.serialize(root)); // 1,2,3,X,X,4,5,X,X,X,X,

        System.out.println(s.deserialize("1,2,3,X,X,4,5,X,X,X,X,").val);
    }

    // dfs
    public class Codec {
        private static final String spliter = ",";
        private static final String nullNode = "X";

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            buildString(root, sb);
            return sb.toString();
        }

        // pre-order traversal
        private void buildString(TreeNode node, StringBuilder sb) {
            if (node == null) {
                sb.append(nullNode).append(spliter);
            } else {
                sb.append(node.val).append(spliter);
                buildString(node.left, sb);
                buildString(node.right, sb);
            }
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            LinkedList<String> nodesList = new LinkedList<>();
            nodesList.addAll(Arrays.asList(data.split(spliter)));
            return buildTree(nodesList);
        }

        private TreeNode buildTree(LinkedList<String> nodes) {
            String val = nodes.removeFirst();
            if (val.equals(nullNode)) {
                return null;
            } else {
                TreeNode node = new TreeNode(Integer.parseInt(val));
                node.left = buildTree(nodes);
                node.right = buildTree(nodes);

                return node;
            }
        }
    }

/*
     1
    / \
   2   3
      / \
     4   5

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

for each parent with index-i, its children index:
    left: 2*i+1
    right: 2*i+2
 */
    public class Codec_bfs {

        private static final String spliter = ",";
        private static final String nullNode = "X";

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {

            if(root == null) {
                return "";
            }

            Queue<TreeNode> q = new LinkedList<>();

            StringBuilder result = new StringBuilder();

            q.offer(root);
            while(!q.isEmpty()) {
                TreeNode current = q.poll();
                if (current != null) {
                    result.append(current.val).append(spliter);
                    q.offer(current.left);
                    q.offer(current.right);
                } else {
                    result.append(nullNode).append(spliter);
                }
            }

            return result.toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {

            String[] nodes = data.split(spliter);

            TreeNode root = null;

            for (int i = 0; 2 * i + 2 < nodes.length; i++) {

                if (nodes[i].equals(nullNode)) {
                    continue;
                }

                TreeNode current = new TreeNode(Integer.parseInt(nodes[i]));

                if (!nodes[2 * i + 1].equals(nullNode)) {
                    current.left = new TreeNode(Integer.parseInt(nodes[2 * i + 1]));
                }

                if (2*i+2 < nodes.length && !nodes[2 * i + 2].equals(nullNode)) {
                    current.right = new TreeNode(Integer.parseInt(nodes[2 * i + 2]));
                }

                if (i == 0) {
                    root = current;
                }

            }
            return root;
        }
    }

}

All Problems

All Solutions