Can any one post a clean level order deserialization?


  • 0
    C

    Tried but haven't come up with a nice idea. Serialization is easy, just normal level order traversal using a queue. What about serialization?

    public class Codec {
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            if(root ==  null) return sb.toString();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                TreeNode cur = queue.poll();
                if(cur == null){
                    sb.append("NULL").append(",");
                    continue;
                }
                sb.append(cur.val).append(",");
                queue.offer(cur.left);
                queue.offer(cur.right);
            }
            return sb.toString();
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            
        }
    }

  • 6
    S

    how about my solution ?

     // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data == null || data.length () == 0) {
                return null ;
            }
            String [] val = data.split(",");
            TreeNode root = new TreeNode (Integer.parseInt (val[0]));
            Queue<TreeNode> q = new LinkedList<> ();
            q.offer(root) ;
            for (int i = 1 ; i < val.length ; i += 2) {
                TreeNode cur = q.poll();
                if (!"#".equals(val[i])) {
                    TreeNode left = new TreeNode (Integer.parseInt (val[i]));
                    cur.left = left ;
                    q.offer (left);
                }
                if (i + 1 < data.length() && !"#".equals(val[i + 1])) {
                    TreeNode right = new TreeNode (Integer.parseInt (val[i + 1]));
                    cur.right = right ;
                    q.offer (right);
                }
            }
            return root ;
        }

  • 0

    Nice! This looks exactly the same as LeetCode OJ's deserialize function. In C++ the code could be shorter using the double pointer trick though.


  • 0

    "Serialization is easy"

    So easy that you screwed it up :-P


  • 0
    H

    Can you post your serialize()? I am searching for a way to avoid adding "#" after the leaves


  • 0
    S

    hope this will be helpful
    // Encodes a tree to a single string.

       public String serialize(TreeNode root) {
            if (root == null) {
                return "";
            }
            Queue<TreeNode> q = new LinkedList<> ();
            q.offer (root) ;
            StringBuilder sb = new StringBuilder ();      
            while (!q.isEmpty()) {
                int size = q.size ();
                for (int i = 0 ; i < size ; ++i) {
                    TreeNode cur = q.poll();
                    if (cur != null) {
                        q.offer (cur.left);
                        q.offer (cur.right);
                    }
                    String val = cur == null ? "#" : String.valueOf(cur.val) ;
                    sb.append (val);
                    sb.append (",");
                }
            }
            sb.setLength (sb.length() - 1);
            return sb.toString();
        }

  • 0
    C

    Aha, that was a shame > <


  • 0
    C

    Thank you Scott, really interesting to consider each of the two child nodes every time : )


  • 0
    H

    Great solution! But I believe your code will also generate "#" children for leave nodes. But it is not a big deal


  • 1
    R

    Serialize and deserialize that produce and consume the string exactly in OJ's format:

    import java.util.StringJoiner;
    
    public class Codec {
    
        public String serialize(TreeNode root) {
            StringJoiner sj = new StringJoiner(",","[","]");
            if (root == null) return sj.toString();
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                TreeNode node = queue.pop();
                if (node == null) {
                    sj.add(null);
                    continue;
                }
                sj.add(""+node.val);
                queue.add(node.left);
                queue.add(node.right);
            }
            return sj.toString().replaceAll("(,null)*]", "]");
        }
    
        public TreeNode deserialize(String data) {
            if (data.equals("[]")) return null;
            String[] nodes = data.substring(1,data.length()-1).split(",");
            TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            for (int i = 1; i<nodes.length; i+=2) {
                TreeNode node = queue.pop();
                if (!nodes[i].equals("null")) {
                    node.left = new TreeNode(Integer.parseInt(nodes[i]));
                    queue.add(node.left);
                }
                if (i+1 < nodes.length && !nodes[i+1].equals("null")) {
                    node.right = new TreeNode(Integer.parseInt(nodes[i+1]));
                    queue.add(node.right);
                }
            }
            return root;
        }
    }
    

  • 0
    X
    This post is deleted!

Log in to reply
 

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