[数据结构与算法] LeetCode——449.序列化和反序列化二叉搜索树

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> LeetCode——449.序列化和反序列化二叉搜索树 -> 正文阅读

[数据结构与算法]LeetCode——449.序列化和反序列化二叉搜索树

通过万岁！！！

题目：就是将一个线索二叉树，进行序列化和反序列化。换句话说，将一个线索二叉树转换成字符串，然后再将这个字符串转换回来。
思路：之前有个题，leetcode1008，就是将一个先序的二叉树数组转换成二叉树，其实已经给我们做完了一般了。我们只需要将二叉树先序存储成字符串就可以了。
技巧：主要是需要了解线索二叉树的特点。

java代码

public class Codec {


    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        // 直接对树进行先序遍历
        List<Integer> list = new ArrayList<>();
        getString(root, list);
        return list.toString();
    }


    public void getString(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        getString(root.left, list);
        getString(root.right, list);
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        // 跟leetcode的1008类似
        if (data.length() == 2) return null;// []的时候
        String substring = data.substring(1, data.length() - 1);
        int[] datas = Arrays.stream(substring.split(", ")).mapToInt(s -> Integer.parseInt(s)).toArray();
        return getTree(datas, 0, datas.length - 1);
    }


    public TreeNode getTree(int[] list, int i, int n) {
        if (i > n) {
            return null;
        }
        TreeNode treeNode = new TreeNode(list[i]);
        int j = i + 1;
        while (j <= n) {
            if (list[j] > list[i]) {
                break;
            }
            j++;
        }
        treeNode.left = getTree(list, i + 1, j - 1);// i+1到j-1是小于
        treeNode.right = getTree(list, j, n);
        return treeNode;
    }
}