Java Easy To Understand O(N^2) Solution


  • 1

    I think there should be O(n) solution which utilize the properties of BST with some boundary MIN/MAX values checking, while I haven't figured them out. Here is somewhat easy to understand O(n^2) solution. If you have done #297, this solution should be obvious.

    public class Codec {
    
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            if (root == null) return sb.toString();
            preorder(root, sb);
            return sb.substring(0, sb.length() - 1);
        }
        private void preorder(TreeNode root, StringBuilder sb) {
            if (root == null) return;
            sb.append(root.val).append("#");
            preorder(root.left, sb);
            preorder(root.right, sb);
        }
    
        public TreeNode deserialize(String data) {
            if (data.isEmpty()) return null;
            String[]arr = data.split("#");
            return buildTree(arr, 0, arr.length - 1);
        }
        private TreeNode buildTree(String[] arr, int l, int r) {
            if (l > r) return null;
            TreeNode root = new TreeNode(Integer.parseInt(arr[l]));
            int splitIndex = findIndex(arr, Integer.parseInt(arr[l]), l + 1, r);
            root.left = buildTree(arr, l + 1, splitIndex - 1);
            root.right = buildTree(arr, splitIndex, r);
            return root;
        }
        private int findIndex(String[] arr, int target, int l, int r) {
            int i = l;
            for (; i <= r; i++) {
                if (Integer.parseInt(arr[i]) > target) break;
            }
            return i;
        }
    }
    

  • 0

    though not fast solution
    I do like the idea of divide and conquer here
    thanks


Log in to reply
 

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