Java Preorder, Inorder, Postorder and Levelorder Serialize and Deserialize


  • 0
    L

    Preorder Serialize and Deserialize

    • Serialize
    public static String preOrderSerialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            preOrderSerializeHelper(root, sb);
            return sb.toString();
        }
    
        private static void preOrderSerializeHelper(TreeNode root, StringBuilder sb) {
            if (root == null) {
                sb.append("# ");
                return;
            }
            sb.append(root.data + " ");
            preOrderSerializeHelper(root.left, sb);
            preOrderSerializeHelper(root.right, sb);
        }
    
    • Deserialize
    public static TreeNode preOrderDeserialize(String input) {
            String[] nums = input.split("\\s+");
            LinkedList<String> list = new LinkedList<>();
            for (String s : nums) {
                list.add(s);
            }
            if (list.size() <= 0) return null;
    
            return preOrderDeserializeHelper(list);
        }
    
        private static TreeNode preOrderDeserializeHelper(LinkedList<String> queue) {
            String val = queue.poll();
            if (val == null || "#".equals(val)) {
                return null;
            }
            TreeNode root = new TreeNode(Integer.parseInt(val));
            root.left = preOrderDeserializeHelper(queue);
            root.right = preOrderDeserializeHelper(queue);
            return root;
        }
    

    Inorder Serialize. we can Deserialize the tree according only Inorder

    public static String inOrderSerialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            inOrderSerializeHelper(root, sb);
            return sb.toString();
        }
    
        private static void inOrderSerializeHelper(TreeNode root, StringBuilder sb) {
            if (root == null) {
                sb.append("# ");
                return;
            }
            inOrderSerializeHelper(root.left, sb);
            sb.append(root.data+" ");
            inOrderSerializeHelper(root.right, sb);
        }
    

    Postorder Serialize and Deserialize

    • Serialize
    public static String postOrderSerialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            postOrderSerializeHelper(root, sb);
            return sb.toString();
        }
    
        private static void postOrderSerializeHelper(TreeNode root, StringBuilder sb) {
            if (root == null) {
                sb.append("# ");
                return;
            }
            inOrderSerializeHelper(root.left, sb);
            inOrderSerializeHelper(root.right, sb);
            sb.append(root.data+" ");
        }
    
    • Deserialize
    public static TreeNode postOrderDeserialize(String input) {
            String[] nums = input.split("\\s+");
            LinkedList<String> list = new LinkedList<>();
            for (int i = nums.length-1; i >= 0; i--) {
                list.add(nums[i]);
            }
            if (list.size() <= 0) return null;
    
            return postOrderDeserializeHelper(list);
        }
    
        private static TreeNode postOrderDeserializeHelper(LinkedList<String> queue) {
            String val = queue.poll();
            if (val == null || "#".equals(val)) {
                return null;
            }
            TreeNode root = new TreeNode(Integer.parseInt(val));
            root.right = postOrderDeserializeHelper(queue);
            root.left = postOrderDeserializeHelper(queue);
            return root;
        }
    

    Levelorder Serialize and Deserialize

    • Serialize
    public static String levelOrderSerialize(TreeNode root) {
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            StringBuilder sb = new StringBuilder();
    
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                if (node == null) {
                    sb.append("# ");
                } else {
                    sb.append(node.data + " ");
                    queue.offer(node.left);
                    queue.offer(node.right);
                }
            }
    
            return sb.toString();
        }
    
    • Deserialize
    public static TreeNode levelOrderDeserialize(String input) {
            String[] data = input.split(" ");
    
            int index = 0;
            if ("#".equals(data[index])) {
                return null;
            }
            int n = Integer.parseInt(data[index++]);
            TreeNode root = new TreeNode(n);
    
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
    
            while (!queue.isEmpty() && index < data.length) {
                TreeNode node = queue.poll();
                if (index < data.length && !"#".equals(data[index])) {
                    TreeNode left = new TreeNode(Integer.parseInt(data[index]));
                    node.left = left;
                    queue.offer(left);
                }
                index++;
                if (index < data.length && !"#".equals(data[index])) {
                    TreeNode right = new TreeNode(Integer.parseInt(data[index]));
                    node.right = right;
                    queue.offer(right);
                }
                index++;
            }
            return root;
        }
    

Log in to reply
 

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