2 concise Java Solutions (O(n) and O(n2)) with using BST's feature (Not the old generic solution for Binary Tree)


  • 0

    Idea:
    We are given a BST, so it is possible to reconstruct the tree by using Pre-Order traverse array.

    Notice we have 1 requirement "The encoded string should be as compact as possible." So let us forget the generic BFS/DFS solution for Binary Tree (Adding "#" or "NULL" for empty node)

    Serialize:
    Very straightforward, simplify do a pre-order traverse and append to String.

    • Version 1: Two lines
        public String serialize(TreeNode root) {
            if (root == null) return "";
            return root.val + "," + serialize(root.left) + serialize(root.right);
        }
    
    • Version 2: Use StringBuilder to save a little bit time.
        public String serialize(TreeNode root) {
            if (root == null) return "";
            StringBuilder sb = new StringBuilder();
            sb.append(root.val).append(",");
            sb.append(serialize(root.left));
            sb.append(serialize(root.right));
            return sb.toString();
        }
    

    Deserialize
    Since we have a pre-order array. We always know the first element is the root.
    So our strategy is to cut the array into different parts by appyling BST feature.

    • Version 1: O(N2)
      1.Passing start bound and end bound to helper function, which means to reconstruct tree in this scope (start ~ end).
      2.Find the first element larger than current root, the first element index will be the middle cutting point. Which means all elements left to it need to be the root.left, all elements right after it need to be root.right. Recursively call the helper function.
        public TreeNode deserialize(String data) {
            if (data == null || data.length() == 0) return null;
            String[] sArr = data.split(",");
            return helper(sArr, 0, sArr.length - 1);
        }
        
        public TreeNode helper(String[] sArr, int start, int end) {
            if (start > end) return null;
            if (start == end) return new TreeNode(Integer.parseInt(sArr[start]));
            TreeNode node = new TreeNode(Integer.parseInt(sArr[start]));
            int mid = start + 1;
            while (mid <= end) {
                if (Integer.parseInt(sArr[mid]) > Integer.parseInt(sArr[start])) {
                    break;
                }
                mid++;
            }
            node.left = helper(sArr, start + 1, mid - 1);
            node.right = helper(sArr, mid, end);
            return node;
        }
    
        public TreeNode deserialize(String data) {
            if (data == null || data.length() == 0) return null;
            String[] sArr = data.split(",");
            int[] currIdx = {0};
            return helper(sArr, currIdx, Integer.MIN_VALUE, Integer.MAX_VALUE);
        }
        
        public TreeNode helper(String[] sArr, int[] currIdx, int min, int max) {
            if (currIdx[0] > sArr.length - 1) return null;
            int curr = Integer.parseInt(sArr[currIdx[0]]);
    
            if (curr < min || curr > max) return null;
    
            TreeNode node = new TreeNode(curr);
            currIdx[0]++;
            node.left = helper(sArr, currIdx, min, curr);
            node.right = helper(sArr, currIdx, curr, max);
            return node;
    
        }

Log in to reply
 

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