@@ -0,0 +1,3346 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport com.freetymekiyan.algorithms.utils.Utils.TreeNode;%0A%0Aimport java.util.Arrays;%0Aimport java.util.HashMap;%0Aimport java.util.Map;%0A%0A/**%0A * 449. Serialize and Deserialize BST%0A * %3Cp%3E%0A * Serialization is the process of converting a data structure or object into a sequence of bits so that it can be%0A * stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the%0A * same or another computer environment.%0A * %3Cp%3E%0A * Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your%0A * serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be%0A * serialized to a string and this string can be deserialized to the original tree structure.%0A * %3Cp%3E%0A * The encoded string should be as compact as possible.%0A * %3Cp%3E%0A * Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms%0A * should be stateless.%0A * %3Cp%3E%0A * Related Topics: Tree%0A * Similar Questions: (H) Serialize and Deserialize Binary Tree, (M) Find Duplicate Subtrees%0A */%0Apublic class SerializeAndDeserializeBst %7B%0A%0A    /**%0A     * Unlike binary tree, binary search tree can be constructed with preorder + inorder traversal.%0A     * So null node can be ignored, thus making the string more compact.%0A     */%0A    public class Codec %7B%0A%0A        private static final String SEPARATOR = %22,%22;%0A%0A        /**%0A         * Get a preorder traversal data.%0A         * Later can be sorted to get inorder traversal.%0A         */%0A        // Encodes a tree to a single string.%0A        public String serialize(TreeNode root) %7B%0A            StringBuilder sb = new StringBuilder();%0A            dfs(root, sb);%0A            return sb.toString();%0A        %7D%0A%0A        private void dfs(TreeNode root, StringBuilder sb) %7B%0A            if (root == null) %7B%0A                return;%0A            %7D%0A            sb.append(root.val).append(SEPARATOR);%0A            dfs(root.left, sb);%0A            dfs(root.right, sb);%0A        %7D%0A%0A        // Decodes your encoded data to tree.%0A        public TreeNode deserialize(String data) %7B%0A            if (data == null %7C%7C data.isEmpty()) %7B%0A                return null;%0A            %7D%0A            int%5B%5D preorder = Arrays.stream(data.split(SEPARATOR)).mapToInt(Integer::parseInt).toArray();%0A            int%5B%5D inorder = Arrays.copyOf(preorder, preorder.length);%0A            Arrays.sort(inorder);%0A            Map%3CInteger, Integer%3E valToIdx = new HashMap%3C%3E();%0A            for (int i = 0; i %3C inorder.length; i++) %7B%0A                valToIdx.put(inorder%5Bi%5D, i);%0A            %7D%0A            return dfs(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1, valToIdx);%0A        %7D%0A%0A        private TreeNode dfs(int%5B%5D preorder, int%5B%5D inorder, int ps, int pe, int is, int ie, Map%3CInteger, Integer%3E valToIdx) %7B%0A            if (ps %3E pe) %7B%0A                return null;%0A            %7D%0A            int rootIdx = valToIdx.get(preorder%5Bps%5D);%0A            TreeNode root = new TreeNode(preorder%5Bps%5D);%0A            root.left = dfs(preorder, inorder, ps + 1, ps + rootIdx - is, is, rootIdx - 1, valToIdx); // x - ps = rootIdx - is%0A            root.right = dfs(preorder, inorder, ps + rootIdx - is + 1, pe, rootIdx + 1, ie, valToIdx);%0A            return root;%0A        %7D%0A    %7D%0A%7D

add 449. Serialize and Deserialize BST