Solution by mengqyou@126.com


  • 0
    M

    Solution

    General idea:

    For BST, we can construct it from only preorder/postorder/levelorder traversal result. However, for the Binary Tree, we cannot. For BT, we have to use preorder with inorder traversal to construct it.

    So here in the serialization process, we can directly serialize BST in preorder, no need to use # or null to represent the null node. → This is the main difference with BT problem LC297.

    Possible bugs:

    1. There is no duplicates in the BST.
    2. We need to use Long.MIN_VALUE and Long.MAX_VALUE as the lower and upper bound to construct the BST since there may be Integer.MIN_VALUE or Integer.MAX_VALUE in the BST.
    Approach #1 (preorder)[Accepted]

    Algorithm

    serialize(): → preorder traversal;

    deserialize(): → reconstruct with preorder traversal by passing (min, max) section.

    Java

    public class Codec {
        private static final String spliter = ",";
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) { // sanity check
                return null;
            }
            StringBuilder sb = new StringBuilder();
            preorder(root, sb);
            return sb.toString();
        }
    
        private void preorder(TreeNode root, StringBuilder sb) {
            if (root == null) {
                return;
            }
            sb.append(root.val).append(spliter);
            preorder(root.left, sb);
            preorder(root.right, sb);
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data == null || data.length() == 0) {
                return null;
            }
            String[] sa = data.split(spliter);
            int[] index = new int[] {0};
            return helper(sa, index, Long.MIN_VALUE, Long.MAX_VALUE);
        }
    
        // construct BST from preorder order traversal;
        private TreeNode helper(String[] sa, int[] index, long min, long max) {
            if (index[0] >= sa.length) {
                return null;
            }
            TreeNode root = null;
            int rootValue = Integer.parseInt(sa[index[0]]);
            if (rootValue > min && rootValue < max) {
                root = new TreeNode(rootValue);
                index[0]++;
                root.left = helper(sa, index, min, rootValue);
                root.right = helper(sa, index, rootValue, max);
            }
            return root;
        }
    }
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec = new Codec();
    // codec.deserialize(codec.serialize(root));
    

    Complexity analysis

    serialize():

    • Time = O(n),
    • Space = O(height), call stack use O(height).

    deserialize():

    • Time = O(n),
    • Space = O(n), call stack costs O(height), but string.split() costs O(n).

    Approach #2 (postorder)[Accepted]

    Algorithm

    serialize(): → postorder traversal;

    deserialize(): → reconstruct with postorder traversal by passing (min, max) section,

    Java

    public class Codec {
        private static final String spliter = ",";
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) { // sanity check
                return null;
            }
            StringBuilder sb = new StringBuilder();
            postorder(root, sb);
            return sb.toString();
        }
    
        private void postorder(TreeNode root, StringBuilder sb) {
            if (root == null) {
                return;
            }
            postorder(root.left, sb);
            postorder(root.right, sb);
            sb.append(root.val).append(spliter);
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data == null || data.length() == 0) {
                return null;
            }
            String[] sa = data.split(spliter);
            int[] index = new int[] {sa.length - 1};
            return helper(sa, index, Long.MIN_VALUE, Long.MAX_VALUE);
        }
    
        // construct BST from preorder order traversal;
        private TreeNode helper(String[] sa, int[] index, long min, long max) {
            if (index[0] < 0) {
                return null;
            }
            TreeNode root = null;
            int rootValue = Integer.parseInt(sa[index[0]]);
            if (rootValue > min && rootValue < max) {
                root = new TreeNode(rootValue);
                index[0]--;
                // build right subtree first due to post-order traversal;
                root.right = helper(sa, index, rootValue, max);
                root.left = helper(sa, index, min, rootValue);
            }
            return root;
        }
    }
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec = new Codec();
    // codec.deserialize(codec.serialize(root));
    

    Complexity analysis

    serialize():

    • Time = O(n),
    • Space = O(height), call stack use O(height).

    deserialize():

    • Time = O(n),
    • Space = O(n), call stack costs O(height), but string.split() costs O(n).

    Approach #3 (levelorder)[Accepted]

    Algorithm

    serialize(): → levelorder traversal;

    deserialize(): → reconstruct with levelorder traversal.
    We need to split level array into two part for their left and right subtree; we cannot use binary search to find the left and right bound since left and right are mixed together.

    Java

    public class Codec {
        private static final String spliter = ",";
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) { // sanity check
                return null;
            }
            StringBuilder sb = new StringBuilder();
            levelorder(root, sb);
            return sb.toString();
        }
    
        private void levelorder(TreeNode root, StringBuilder sb) {
            if (root == null) {
                return;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                sb.append(cur.val).append(spliter);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data == null || data.length() == 0) {
                return null;
            }
            String[] sa = data.split(spliter);
            // transfer level into list since we don't know the size of left and right subtree;
            List<Integer> level = new ArrayList<>();
            for (String s : sa) {
                level.add(Integer.parseInt(s));
            }
            return helper(level);
        }
    
        // construct BST from levelorder order traversal;
        private TreeNode helper(List<Integer> level) {
            if (level.size() == 0) {
                    return null;
            }
            // build root node
            int rootValue = level.get(0);
            TreeNode root = new TreeNode(rootValue);
            // split the level into left and right;
            List<Integer> left = new ArrayList<>();
            List<Integer> right = new ArrayList<>();
            for (int num : level) {
                if (num < rootValue) {
                    left.add(num);
                } else if (num > rootValue) {
                    right.add(num);
                }
            }
            // build the left and right subtree;
            root.left = helper(left);
            root.right = helper(right);
            // return current root to its parent;
            return root;
        }
    }
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec = new Codec();
    // codec.deserialize(codec.serialize(root));
    

    Complexity analysis

    serialize():

    • Time = O(n),
    • Space = O(n), level list costs O(n).

    deserialize():

    • Time = O(n^2), at each level, we need to traverse the whole list to split left and right;
    • Space = O(n^2), call stack costs O(height), but at each level, we need to use O(n) to store left and right list, there are totally O(height) layer. The worst case of O(height) = O(n). So the total space is O(n^2).

    Discussion

    Preorder and postorder solution (beat more than 97%) are much faster than level order (11%). The reason to put level order traversal solution here is just to show that we can do it in that way. The prefer solution is preorder or postorder traversal.


Log in to reply
 

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