LeetCode_二叉搜索树_中等_449.序列化和反序列化二叉搜索树

r囧r小猫 2023-10-15 16:02 11阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。

设计一个算法来序列化和反序列化二叉搜索树。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。

编码的字符串应尽可能紧凑。

**示例 1：**  
输入：root = \[2,1,3\]  
输出：\[2,1,3\]

**示例 2：**  
输入：root = \[\]  
输出：\[\]

**提示：**  
树中节点数范围是 \[0, 104\]  
0 <= Node.val <= 104  
题目数据保证输入的树是一棵二叉搜索树。

## 2.思路 ##

（1）前序遍历

相关题目：  
[LeetCode\_二叉树\_困难\_297.二叉树的序列化与反序列化][LeetCode_297.]

## 3.代码实现（Java） ##

//思路1————前序遍历
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Codec {
        
    
        String SEP = ",";
        String NULL = "null";
    
        // 序列化二叉搜索树为字符串
        public String serialize(TreeNode root) {
        
            if (root == null) {
        
                return "";
            }
            StringBuilder builder = new StringBuilder();
            serializeHelper(root, builder);
            return builder.toString();
        }
        
        private void serializeHelper(TreeNode node, StringBuilder builder) {
        
            if (node == null) {
        
                builder.append(NULL).append(SEP);
                return;
            }
            builder.append(node.val).append(SEP);
            serializeHelper(node.left, builder);
            serializeHelper(node.right, builder);
        }
        
        // 将字符串反序列化为二叉搜索树
        public TreeNode deserialize(String data) {
        
            if (data == null || data.isEmpty()) {
        
                return null;
            }
            Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(",")));
            return deserializeHelper(nodes);
        }
        
        private TreeNode deserializeHelper(Queue<String> nodes) {
        
    	    //取出队首元素
            String valStr = nodes.poll();
            if (valStr.equals(NULL)) {
        
                return null;
            } 
            int val = Integer.parseInt(valStr);
            TreeNode node = new TreeNode(val);
            node.left = deserializeHelper(nodes);
            node.right = deserializeHelper(nodes);
            return node;
        }
    }
    
    // Your Codec object will be instantiated and called as such:
    // Codec ser = new Codec();
    // Codec deser = new Codec();
    // String tree = ser.serialize(root);
    // TreeNode ans = deser.deserialize(tree);
    // return ans;

[LeetCode_297.]: https://xgqngu.blog.csdn.net/article/details/123847555