Force deduction solution summary 449 serialization and deserialization binary search tree

  Directory links ：

Force buckle programming problem - The solution sums up _ Share + Record -CSDN Blog

GitHub Synchronous question brushing items ：

https://github.com/September26/java-algorithms

Original link ： Power button

describe ：

Serialization is the process of converting a data structure or object into a series of bits , So that it can be stored in a file or memory buffer , Or through a network link , To rebuild later in the same or another computer environment .

Design an algorithm to serialize and deserialize Binary search tree . On serialization / There is no limit to how the deserialization algorithm works . You just need to make sure that the binary search tree can be serialized into strings , And the string can be deserialized into the original binary search tree .

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 ：[]
 

Tips ：

The range of nodes in the tree is [0, 104]
0 <= Node.val <= 104
Subject data Guarantee The input tree is a binary search tree .
Pass times 27,875 Submit the number 47,327

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/serialize-and-deserialize-bst
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking ：

*  Their thinking ：
*  We can solve the problem according to the concept of sequence traversal .
*  When serializing , Each time we traverse the current level , Record the next level , At the same time, the string of the next level is generated . If the next level is not all empty , Then add it to the last string .
*  When deserializing , We also set two list To record , Record the current level and the next level respectively . With "," Split string , Number of iterations per time , Twice as much as the previous level （ Not included as null The situation of ）.

Code ：

public class Solution449 {

    public static class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) {
                return "";
            }
            List<TreeNode> treeNodes = new ArrayList<>();
            List<TreeNode> nextNodes = new ArrayList<>();
            treeNodes.add(root);
            StringBuilder builder = new StringBuilder();
            builder.append(root.val);
            builder.append(",");
            StringBuilder lineBuilder = new StringBuilder();
            while (treeNodes.size() > 0) {
                builder.append(lineBuilder);
                lineBuilder.setLength(0);
                nextNodes.clear();
                for (TreeNode node : treeNodes) {
                    if (node.left != null) {
                        lineBuilder.append(node.left.val);
                        lineBuilder.append(",");
                        nextNodes.add(node.left);
                    } else {
                        lineBuilder.append("#,");
                    }

                    if (node.right != null) {
                        lineBuilder.append(node.right.val);
                        lineBuilder.append(",");
                        nextNodes.add(node.right);
                    } else {
                        lineBuilder.append("#,");
                    }
                }
                treeNodes.clear();
                treeNodes.addAll(nextNodes);
            }
            return builder.toString();
        }


        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data.length() == 0) {
                return null;
            }
            String[] split = data.split(",");
            TreeNode root = null;
            List<TreeNode> treeNodes = new ArrayList<>();
            List<TreeNode> nextNodes = new ArrayList<>();
            int base = 1;
            int start = 0;
            while (start < split.length) {
                nextNodes.clear();
                for (int i = 0; i < base; i++) {
                    if (start + i >= split.length) {
                        break;
                    }
                    String value = split[start + i];
                    if (root == null) {
                        root = new TreeNode(Integer.parseInt(value));
                        nextNodes.add(root);
                        continue;
                    }
                    if (value.equals("#")) {
                        continue;
                    }
                    TreeNode currentNode = new TreeNode(Integer.parseInt(value));
                    TreeNode parent = treeNodes.get(i / 2);
                    if (i % 2 == 0) {
                        parent.left = currentNode;
                    } else {
                        parent.right = currentNode;
                    }
                    nextNodes.add(currentNode);
                }
                start = start + base;
                base = nextNodes.size() * 2;
                treeNodes.clear();
                treeNodes.addAll(nextNodes);
                System.out.print("");
            }
            return root;
        }
    }
}