449. Serialize and Deserialize BST

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Serialization is converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You need to ensure that a binary search tree can be serialized to a string, and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Example 1:

Input: root = [2,1,3]
Output: [2,1,3]

Example 2:

Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 104].
• 0 <= Node.val <= 104
• The input tree is guaranteed to be a binary search tree.

Code

public class Codec {
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        preorder(root, sb);
        return sb.toString();
    }
    
    public TreeNode deserialize(String data) {
        Queue<Integer> queue = new LinkedList<>();

        int i = 0;
        while(i + 4 <= data.length()) {
            int num = stringToInt(data.substring(i, i + 4));
            queue.add(num);
            i += 4;
        }

        return helper(Integer.MIN_VALUE, Integer.MAX_VALUE, queue);
    }
    
    public void preorder(TreeNode root, StringBuilder sb) {
        if (root == null) return;
        
        sb.append(intToString(root.val));
        
        preorder(root.left, sb);
        preorder(root.right, sb);
    }

    public TreeNode helper(Integer lower, Integer upper, Queue<Integer> queue) {
        if (queue.isEmpty()) return null;
        
        int val = queue.peek();
        
        if (val < lower || val > upper) return null;
        
        queue.poll();

        TreeNode root = new TreeNode(val);
        root.left = helper(lower, val, queue);
        root.right = helper(val, upper, queue);
        
        return root;
    }
    
    public String intToString(int x) {
        char[] res = new char[4];
        
        for (int i = 0; i < 4; i++) {
            res[i] = (char) (x >> (i * 8) & 0xff);
        }
        
        return new String(res);
    }

    public int stringToInt(String s) {
        int res = 0;
        char[] charArr = s.toCharArray();
        for(int i = 0; i < 4; i++){
            int num = (int)charArr[i];
            res += num << (i * 8);
        }
        return res;
    }
}

297. Serialize and Deserialize Binary Tree

public class Codec {
    public String serialize(TreeNode root) {
        if(root == null) return "";
        
        StringBuilder res = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        
        queue.offer(root);

        /*
            3
           / \
          2   4
         /   /
        1   5

        3 2 4 1 null 5 null null null null null
        */
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            
            if(node == null){
                res.append("null ");
                continue;
            }

            res.append(node.val + " ");
            queue.offer(node.left);
            queue.offer(node.right);
        }

        return res.toString();
    }

    public TreeNode deserialize(String data) {
        if(data == null || data.length() == 0) return null;

        String[] strs = data.split(" ");
        TreeNode root = new TreeNode(Integer.valueOf(strs[0]));

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        for(int i = 1; i < strs.length; i++){
            TreeNode node = queue.poll();
            
            if(!strs[i].equals("null")){
                node.left = new TreeNode(Integer.valueOf(strs[i]));
                queue.offer(node.left);
            }

            i++;

            if(!strs[i].equals("null")){
                node.right = new TreeNode(Integer.valueOf(strs[i]));
                queue.offer(node.right);
            }
        }
        
        return root;
    }
}