LeetCode刷题【449】序列化和反序列化二叉搜索树

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

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

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

 

示例 1：

输入：root = [2,1,3]
输出：[2,1,3]

示例 2：

输入：root = []
输出：[]

 

提示：

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

 

注意：不要使用类成员/全局/静态变量来存储状态。 你的序列化和反序列化算法应该是无状态的。

\n

题解

因为这是一棵搜索树，利用前序遍历的特性就可以，还原过程和之前的LeetCode刷题【1008】前序遍历构造二叉搜索树样

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    List<Integer> list;

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        list = new ArrayList<>();
        dfs(root);
        return listToString();
    }

    //先序遍历记录内容
    public void dfs(TreeNode root){
        if (root == null) {
            return;
        }
        list.add(root.val);
        dfs(root.left);
        dfs(root.right);
    }

    public String listToString(){
        if (list.size()==0){
            return "";
        }
        StringBuilder str = new StringBuilder(""+list.get(0));
        for (int i = 1; i < list.size(); i++) {
            str.append(",").append(list.get(i));
        }
        return str.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data==null || data.length()==0){
            return null;
        }
        list = new ArrayList<>();
        String[] arr = data.split(",");
        for (String num : arr) {
            list.add(Integer.parseInt(num));
        }
        return deserializeByPreOrder(0,arr.length-1);
    }

    public TreeNode deserializeByPreOrder(int left, int right){
        if (left>right){
            return null;
        }
        TreeNode node = new TreeNode(list.get(left));
        if (left==right){
            return node;
        }
        //找到比node大的那个值为右子树的根节点
        int rightBegin = left;
        left++;
        while (rightBegin<=right && list.get(rightBegin) <= node.val){
            rightBegin++;
        }
        node.left = deserializeByPreOrder(left,rightBegin-1);
        node.right = deserializeByPreOrder(rightBegin,right);
        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 submit region end(Prohibit modification and deletion)

因为是二叉搜索树，有着明显的大小值有序的特性。

如果换成是普通的二叉树，可以用BFS的方式序列化处理。null节点使用特殊非数字的字符替代即可或者直接留空可以，解析的时候同样按“,”逗号分割，如果得到的是空字符串则表示null。

还有一个通用二叉树的思路，比如有二叉树如下

             5
           /   \
          4     7
         /     / \
         2   6   8
          \
          3

按照结构序列化如下，使用“[”“]”“,”来分割表示

5[4[,2[,3]],],7[6,8]]

借助栈的先进后出的特性，来实现，分析过程如下

• 读取到5，构建一个val为5的node节点入栈，此时栈内元素【5】
• 读取到4，继续构建入栈，此时栈内元素【4,5】
• 读取到一个空节点，构建个空节点入栈，此时栈内元素【null,4,5】
• 读取到2，构建一个2节点入栈，此时栈内元素【2,null,4,5】
• 读取到一个空节点，构建一个空节点入栈，此时栈内元素【null,2,null,4,5】
• 读取到3，构建个3节点入栈，此时栈内元素【3,null,2,null,4,5】
• 接下来是关键，遇到了“]”字符，取出栈顶两个元素，依次分别为取出后栈顶元素的右节点和左节点，即3节点为2节点的右子节点，null节点为2节点的左子节点。此时栈内元素【2,null,4,5】，2下面挂靠了null和3节点
• 接下来又遇到了“]”字符，同样取出栈顶两个元素，挂靠到对应节点下面，即2节点挂到4节点的右子节点位置，null节点挂在4节点的左子节点位置，此时栈内元素【4,5】
• 之后继续遇到了7，创建节点并入栈。【7,4,5】
• 又分别遇到了6和7，继续入栈。【8,6,7,4,5】
• 再次遇到“]”，把弹出放在7节点下。此时栈内剩下【7,4,5】
• 再次遇到“]”，把7、4节点弹出放在5节点下
• 最终结束二叉树构建完成