Java Solution with queue


  • 5
    R

    Use two queues swap for binary traversal, for any null node, append "null". For deserialisation, split the string with space, again use queue to construct the tree. The code is as below:

    public class Codec {
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            // if(root==null) return "";
            StringBuilder sb = new StringBuilder();
            Queue<TreeNode> parent = new LinkedList<>();
            parent.offer(root);
            while(!parent.isEmpty()) {
                Queue<TreeNode> children = new LinkedList<>();
                while(!parent.isEmpty()) {
                    TreeNode node = parent.poll();
                    if(node!=null) {
                        sb.append(node.val);
                        children.offer(node.left);
                        children.offer(node.right);
                    } else {
                        sb.append("null");
                    }
                    sb.append(" ");
                }
                parent = children;
            }
            return sb.toString().trim();
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            String[] strs = data.split(" ");
            Queue<TreeNode> parent = new LinkedList<>();
            TreeNode root = strs[0].equals("null") ? null : new TreeNode(Integer.valueOf(strs[0]));
            parent.offer(root);
            int i = 1;
            while(!parent.isEmpty()) {
                Queue<TreeNode> children = new LinkedList<>();
                while(!parent.isEmpty()) {
                    TreeNode node = parent.poll();
                    if(node!=null) {
                        if(i< strs.length && !strs[i].equals("null")){
                            node.left = new TreeNode(Integer.valueOf(strs[i++]));
                        } else {
                            i++;
                        }
                        if(i< strs.length && !strs[i].equals("null")){
                            node.right = new TreeNode(Integer.valueOf(strs[i++]));
                        } else {
                            i++;
                        }
                        children.offer(node.left);
                        children.offer(node.right);
                    }
                }
                parent = children;
            }
            return root;
        }
    }

  • 0
    F

    Great solution, I think level order is better than the pre-order one in terms of total size for transmitting.
    Also, I think we can also use 1 queue rather than 2 queues, by looping the queue with saved size so no matter offering during looping.

    public TreeNode deserialize(String data) {
        String[] strs = data.split(",");
        Queue<TreeNode> q = new LinkedList<>();
        TreeNode root = strs[0].equals("null") ? null : new TreeNode(Integer.valueOf(strs[0]));
        q.offer(root);
        int i = 1;
        while(!q.isEmpty()) {
          int sz = q.size();
          for (int j = 0; j< sz; ++j) {  // the only change
            TreeNode node = q.poll();
            if(node!=null) {
              if(i< strs.length && !strs[i].equals("null")){
                node.left = new TreeNode(Integer.valueOf(strs[i++]));
              } else {
                i++;
              }
              if(i< strs.length && !strs[i].equals("null")){
                node.right = new TreeNode(Integer.valueOf(strs[i++]));
              } else {
                i++;
              }
              q.offer(node.left);
              q.offer(node.right);
            }
          }
        }
        return root;
      }

  • 0
    M

    Here is my version and it is a bit easy to understand.

    public class Codec {
    
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if (root == null)
            return sb.append("null").toString();
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        while (!que.isEmpty()) {
            TreeNode node = que.remove();
            if (node != null) {
                sb.append(node.val).append(",");
                que.add(node.left);
                que.add(node.right);
            } else {
                sb.append("null").append(",");
            }
        }
        return sb.toString();
    }
    
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        List<String> list = new ArrayList<>();
        list.addAll(Arrays.asList(data.split(",")));
        String val = list.remove(0);
        TreeNode root = val.equals("null")?null:new TreeNode(Integer.parseInt(val));
        if (root == null) return root;
        
        Queue<TreeNode> que = new ArrayDeque<>();
        que.add(root);
        while(!que.isEmpty()) {
            TreeNode node = que.remove();
            val = list.remove(0);
            if (val.equals("null")) {
                node.left = null;
            } else {
                node.left = new TreeNode(Integer.parseInt(val));
                que.add(node.left);
            }
            val = list.remove(0);
            if (val.equals("null")) {
                node.right = null;
            } else {
                node.right = new TreeNode(Integer.parseInt(val));
                que.add(node.right);
            }
        }        
        return root;
    }
    }

Log in to reply
 

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