my BFS solution with O(n) in serialization and deserialization, easy to understand


  • 0
    Y

    public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null){
            return "";
        }
        StringBuilder sb = new StringBuilder();
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offerLast(root);
        sb.append(root.val + ",");
        while(!deque.isEmpty()){
            TreeNode node = deque.pollFirst();
            if(node.left == null){
                sb.append("*,");
            }
            else{
                sb.append(node.left.val + ",");
                deque.offerLast(node.left);
            }
            if(node.right == null){
                sb.append("*,");
            }
            else{
                sb.append(node.right.val + ",");
                deque.offerLast(node.right);
            }
        }
        System.out.println(sb.toString());
        return sb.toString();
    }
    
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null || data.length() == 0){
            return null;
        }
        String[] vals = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.offerLast(root);
        int i = 1;
        //System.out.println(vals[1]);
        while(!deque.isEmpty()){
            TreeNode node = deque.pollFirst();
            if(vals[i].equals("*")){
                node.left = null;
            }
            else{
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                deque.offerLast(node.left);
            }
            i++;
            if(vals[i].equals("*")){
                node.right = null;
            }
            else{
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                deque.offerLast(node.right);
            }
            i++;
        }
        return root;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.