Easy to understand Java Solution


  • 198
    G

    The idea is simple: print the tree in pre-order traversal and use "X" to denote null node and split node with ",". We can use a StringBuilder for building the string on the fly. For deserializing, we use a Queue to store the pre-order traversal and since we have "X" as null node, we know exactly how to where to end building subtress.

    public class Codec {
        private static final String spliter = ",";
        private static final String NN = "X";
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            buildString(root, sb);
            return sb.toString();
        }
    
        private void buildString(TreeNode node, StringBuilder sb) {
            if (node == null) {
                sb.append(NN).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) {
            Deque<String> nodes = new LinkedList<>();
            nodes.addAll(Arrays.asList(data.split(spliter)));
            return buildTree(nodes);
        }
        
        private TreeNode buildTree(Deque<String> nodes) {
            String val = nodes.remove();
            if (val.equals(NN)) return null;
            else {
                TreeNode node = new TreeNode(Integer.valueOf(val));
                node.left = buildTree(nodes);
                node.right = buildTree(nodes);
                return node;
            }
        }
    }

  • -10
    J

    if there is no data between two commas, it means nullptr

    class Codec {
    public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string Result;
        PreOrderVisit(root, Result);
        return Result;
    }
    void PreOrderVisit(TreeNode* root, string& Result){
        if(nullptr == root){
            Result += ",";
            return;
        }
        Result += to_string(root->val)+',';
        PreOrderVisit(root->left, Result);
        PreOrderVisit(root->right, Result);
    }
    
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        auto Begin = data.begin();
        auto End = data.end();
        return BuildPreOrderVisit(Begin, End);
    }
    TreeNode* BuildPreOrderVisit(string::iterator& Begin, string::iterator End){
        auto CommaPos = find(Begin, End, ',');
        if(CommaPos == Begin){
            Begin = CommaPos+1;
            return nullptr;
        }
        
        string Num(Begin, CommaPos);
        auto pNode = new TreeNode(atoi(Num.c_str()));
        Begin = CommaPos+1;
        pNode->left = BuildPreOrderVisit(Begin, End);
        pNode->right = BuildPreOrderVisit(Begin, End);
        return pNode;
    }
    

    };


  • 2

    Cool pre-order traversal and recursive codes!


  • 2
    G

    It won't be possible to have no data between commas because I used 'X' for null nodes when I am serializing. If such a use case exists it means that it's not serialized by this code and sure it won't de-serialize correctly


  • 9
    W

    Why use deque not queue?


  • 0
    C

    no need, you can try


  • 0
    B

    DFS solution will take too much redundant space.


  • 0
    R

    Nice solution. Can you confirm what the time complexity of your solution is?
    I'm not quite sure but is the serialization in O(n) and deserialization in O(nlogn)? Also the space would be O(n)?


  • 0
    I

    That solution is great. But just keep in mind at the end of the encoded String also has a splitter, though it has no effect on the results.


  • 0
    B

    One problem will be: if the tree has a lot of NULL node, you will waste a lot of space. For a tree that all nodes have right child as NULL, you store N nodes, but actually log(N) needed.

    My solution is to have all non-NULL nodes in pre-order list and store one nodes as (Val, index of left child in the list, index of right child in the list).

        class Node {
          int val, left, right;
          Node(int v) {
            val = v;
            left = right = -1;
          }
        }
        
        private List<Node> nodeList = new ArrayList<>();
    
        private int serializeInt(TreeNode node) {
          nodeList.add(new Node(node.val));
          int myInd = nodeList.size() - 1;
          if (node.left != null)
            nodeList.get(myInd).left = serializeInt(node.left);
          if (node.right != null)
            nodeList.get(myInd).right = serializeInt(node.right);
          return myInd;
        }
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
          if (root == null)
            return "";
    
          nodeList.clear();
          serializeInt(root);
    
          StringBuilder sb = new StringBuilder();
          StringJoiner sj = new StringJoiner(",");
          for (int i = 0; i < nodeList.size(); i++) {
            Node n = nodeList.get(i);
            sb.append(n.val)
                    .append("#")
                    .append(n.left)
                    .append("#")
                    .append(n.right);
            sj.add(sb);
            sb.setLength(0);
          }
          return sj.toString();
        }
    
        private TreeNode deserializeInt(String[] nodes, int myInd) {
          String[] data = nodes[myInd].split("#");
          TreeNode node = new TreeNode(Integer.valueOf(data[0]));
          if (!data[1].equals("-1"))
            node.left = deserializeInt(nodes, Integer.valueOf(data[1]));
          if (!data[2].equals("-1"))
            node.right = deserializeInt(nodes, Integer.valueOf(data[2]));
          return node;
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
          if (data == null || data.equals(""))
            return null;
          return deserializeInt(data.split(","), 0);
        }
    

  • 26

    Good idea! Could be more concise though. Thanks for sharing!

        public String serialize(TreeNode root) {
            return serial(new StringBuilder(), root).toString();
        }
        
        // Generate preorder string
        private StringBuilder serial(StringBuilder str, TreeNode root) {
            if (root == null) return str.append("#");
            str.append(root.val).append(",");
            serial(str, root.left).append(",");
            serial(str, root.right);
            return str;
        }
    
        public TreeNode deserialize(String data) {
            return deserial(new LinkedList<>(Arrays.asList(data.split(","))));
        }
        
        // Use queue to simplify position move
        private TreeNode deserial(Queue<String> q) {
            String val = q.poll();
            if ("#".equals(val)) return null;
            TreeNode root = new TreeNode(Integer.valueOf(val));
            root.left = deserial(q);
            root.right = deserial(q);
            return root;
        }
    

  • 9

    alt text


  • 3

    said in Easy to understand Java Solution:

    Deque<String> nodes

    Why do choose to use Deque ?


  • -2

    @Zura Because Queue cannot store null, while Deque can.


  • 2

    @jianchao.li.fighter
    Hi jianchao li,

    I have a question actually, using his code, when deserializing String "1,2,3,null,null,4,5" to tree, we got:

                         1
                        /
                      2
                    /   \
                  3      4
    

    When I first saw his code, I got confused, because I feel something wrong with his recursion of the second part - deserializing part. His method is always recurse left first one node by one node, that is to say, those right nodes are also possibly could be deserialized to left part.

    So I tried it on my IDE, the result is shown above, all nodes 2,3,4 become left children of 1.

    Well, the most confusing thing is that there are some other mistakes in his code, however his solution passed all the test cases and got Accepeted. For example, String val = nodes.remove(); is actually wrong, because it should not be null if we choose to use remove(), instead, we should use poll() or something else, here, nodes could be null when we reach the end.

    If we use remove() here:

    Exception in thread "main" java.util.NoSuchElementException

    Did I misunderstand something?

    Thank you!


  • 0

    @zhugejunwei Below is my code:

    public class Codec {
        // serialize
        public String serialize(TreeNode root) {
            if (root == null) return "";
            LinkedList<TreeNode> q = new LinkedList<TreeNode>();
            TreeNode node = root;
            q.add(node);
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            int level = 1;
            while (!q.isEmpty()) {
                TreeNode cur = q.poll();
                if (cur != null) {
                    sb.append(cur.val).append(",");
                    q.offer(cur.left);
                    q.offer(cur.right);
                } else {
                    sb.append("null,");
                }
            }
            sb.deleteCharAt(sb.length() - 1);
            while (sb.length() > 4 && sb.substring(sb.length() - 4).toString().equals("null")) {
                sb = sb.delete(sb.length() - 4, sb.length());
                sb.deleteCharAt(sb.length() - 1);
            }
            sb.append("]");
            return sb.toString();
        }
        
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data == null || data.length() == 0) return null;
            data = data.substring(1, data.length() - 1);
            String[] arr = data.split(",");
            TreeNode root = new TreeNode(Integer.valueOf(arr[0]));
            
            LinkedList<TreeNode> q = new LinkedList<TreeNode>();
            q.add(root);
            int i = 1;
            while (!q.isEmpty()) {
                TreeNode pre = q.poll();
                if (pre == null) {
                    continue;
                }
                if (i < arr.length && !arr[i].equals("null")) {
                    pre.left = new TreeNode(Integer.valueOf(arr[i]));
                } else {
                    pre.left = null;
                }
                q.offer(pre.left);
                i++;
                if (i < arr.length && !arr[i].equals("null")) {
                    pre.right = new TreeNode(Integer.valueOf(arr[i]));
                } else {
                    pre.right = null;
                }
                q.offer(pre.right);
                i++;
            }
            return root;
        }
    }
    
    

  • 0
    S

    said in Easy to understand Java Solution:

    private TreeNode buildTree(Deque<String> nodes) {
    String val = nodes.remove();
    if (val.equals(NN)) return null;
    else {
    TreeNode node = new TreeNode(Integer.valueOf(val));
    node.left = buildTree(nodes);
    node.right = buildTree(nodes);
    return node;
    }
    }

    Why nodes.remove() won't through NoSuchElementException when nodes is empty?


  • 0
    S

    @Sining I got it


  • 0
    G

    I think the queue may not be necessary. So can you tell me why do you use a queue?


  • 0
    A

    @Sining I have the same doubt. Did you get an answer to this?


Log in to reply
 

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