Serialize and Deserialize Binary Tree

Solution 1)

Using a BFS, make a string by traversing by BFS.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
        left = right = null;
    }

    public static String serialize(TreeNode root) {
        if (root == null) return "";
        Queue<TreeNode> queue = new LinkedList<>();
        StringBuffer sb = new StringBuffer();
        queue.add(root);
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                sb.append(node.val+",");
                queue.add(node.left);
                queue.add(node.right);
            } else {
                sb.append("*,");
            }
        }
        String s = sb.toString();
        return s.substring(0,s.length()-1);
    }

    public static TreeNode deserialize(String s) {
        if (s == null || s.length() == 0) return null;
        if (s.length() == 1 && s == "*") return null;
        Queue<TreeNode> queue = new LinkedList<>();        
        String strs[] = s.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
        queue.add(root);
        int i = 1;
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (!strs[i].equalsIgnoreCase("*")) {
                node.left = new TreeNode(Integer.parseInt(strs[i]));
                queue.add(node.left);
            }
            i++;
            if (!strs[i].equalsIgnoreCase("*")) {
                node.right = new TreeNode(Integer.parseInt(strs[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;

    }

    public static void printTree(TreeNode root) {
        if (root == null) System.out.println("");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            Queue<TreeNode> queue2 = new LinkedList<>();
            while(!queue.isEmpty()) {
                TreeNode node = queue.poll();

                if (node != null) {
                    System.out.print("("+node.val+")");
                    queue2.add(node.left);
                    queue2.add(node.right);
                } else {
                    System.out.print("(*)");
                }
            }
            System.out.println();
            queue = queue2;
        }
    }

    public static void main(String args[]) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        root.left.left.right = new TreeNode(8);
        root.left.right.right = new TreeNode(9);
        root.right.right.left = new TreeNode(10);
        root.right.right.right = new TreeNode(11);

        printTree(root);
        String s = serialize(root);
        System.out.println(s);
        TreeNode newRoot = deserialize(s);
        printTree(newRoot);
    }
}

Solution 2)

Using a preorder traversing, make a string

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
        left = right = null;
    }

    public static String serialize(TreeNode root) {
        if (root == null) return "*";
        Stack<TreeNode> stack = new Stack<>();
        StringBuffer sb = new StringBuffer();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            sb.append(node.val+",");
            sb.append(serializePreorder(node.left)+",");
            sb.append(serializePreorder(node.right)+",");
        }
        String s = sb.toString();
        return s.substring(0,s.length()-1);
    }

    public static TreeNode helper(String s[], int[] t) {
        if (s[t[0]].equalsIgnoreCase("*")) return null;
        TreeNode node = new TreeNode(Integer.parseInt(s[t[0]]));
        t[0] = t[0] + 1;
        node.left = helper(s, t);
        t[0] = t[0] + 1;
        node.right = helper(s,t);
        return node;
    }

    public static TreeNode deserialize(String s) {
        if (s == null || s.length() == 0) return null;
        if (s.length() == 1 && s == "*") return null;
        return helper(s.split(","),new int[] {0});        
    }

    public static String serialize(TreeNode root) {
        if (root == null) return "";
        Queue<TreeNode> queue = new LinkedList<>();
        StringBuffer sb = new StringBuffer();
        queue.add(root);
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                sb.append(node.val+",");
                queue.add(node.left);
                queue.add(node.right);
            } else {
                sb.append("*,");
            }
        }
        String s = sb.toString();
        return s.substring(0,s.length()-1);
    }

    public static void printTree(TreeNode root) {
        if (root == null) System.out.println("");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            Queue<TreeNode> queue2 = new LinkedList<>();
            while(!queue.isEmpty()) {
                TreeNode node = queue.poll();

                if (node != null) {
                    System.out.print("("+node.val+")");
                    queue2.add(node.left);
                    queue2.add(node.right);
                } else {
                    System.out.print("(*)");
                }
            }
            System.out.println();
            queue = queue2;
        }
    }

    public static void main(String args[]) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        root.left.left.right = new TreeNode(8);
        root.left.right.right = new TreeNode(9);
        root.right.right.left = new TreeNode(10);
        root.right.right.right = new TreeNode(11);

        printTree(root);
        String s = serialize(root);
        System.out.println(s);
        TreeNode newRoot = deserialize(s);
        printTree(newRoot);
    }
}