Java 20ms Explained


  • 0
    M

    This solution uses preorder traversal followed by sequential decoding.

    Serialize: We can very simply store the preorder of a tree using an ArrayList. When a non-null node is reached, it is added to the end of the ArrayList. This program uses iterative traversal with a Stack.

    Deserialize: Deserializing the String version of a tree can be done with recursion. We must iterate over the values we are given while preserving the BST property, that a node is >= its left and is <= its right. Also recall that since we serialized with preorder, we can attempt to deserialize with preorder.

    But how do we keep track of the value we are currently trying to insert? Since the program stated we cannot use global variables, we need some way to track our position. The queue data structure is optimal because it automatically tracks which value is next. Simply insert the front of the queue in the current position if its value is valid at the current position; that is, its value lies between [min, max].

     class Codec {
        
        private static final String EMPTY_STRING = "";
        private static final String DELIMETER = " ";
    
        // Encodes a tree to a single string.
        /**
         * Explanation: this does a simple preorder traversal. Uses an
         * ArrayList to store the traversal. Transfers data from the
         * ArrayList to a returned String once the traversal is done.
         */
        public String serialize(TreeNode root) {
            ArrayList<Integer> list = new ArrayList<Integer>();
            
            if (root != null) {
                Stack<TreeNode> s = new Stack<TreeNode>();
                s.push(root);
                
                while (!s.isEmpty()) {
                    TreeNode t = s.pop();
                    list.add(t.val);
                    
                    if (t.right != null) {
                        s.push(t.right);
                    }
                    if (t.left != null) {
                        s.push(t.left);
                    }
                }
            }
            
            if (list.size() == 0) return EMPTY_STRING;
            
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < list.size(); i++) {
                sb.append(list.get(i));
                sb.append(DELIMETER);
            }
                
            return sb.toString();
        }
    
        // Decodes your encoded data to tree.
        /**
         * Explanation: creates a tree using the BST-range technique.
         * At each step, the next value in the queue must be in the
         * valid interval [min, max] to return a new node (otherwise,
         * a null is returned to stop that branch.) The queue data
         * structure internalizes the data array-pointer combo, which
         * would otherwise be a global variable pair.
         */ 
        public TreeNode deserialize(String data) {
            
            if (data.equals(EMPTY_STRING)) return null;
            
            String[] s = data.split(DELIMETER);
            Queue<Integer> q = new LinkedList<Integer>();
            
            for (int i = 0; i < s.length; i++) {
                q.add(Integer.parseInt(s[i]));
            }
            
            TreeNode tree = deserializeHelper(q, Integer.MIN_VALUE, Integer.MAX_VALUE);
            
            return tree;
        }
        
        private TreeNode deserializeHelper(Queue<Integer> q, int min, int max) {
            if (!q.isEmpty()) {
                Integer i = q.peek();
                if ((i >= min) && (i <= max)) {
                    i = q.poll();
                    TreeNode t = new TreeNode(i);
                    t.left = deserializeHelper(q, min, i);
                    t.right = deserializeHelper(q, i, max);
                    return t;
                }
            }
            return null;
        }
    }

Log in to reply
 

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