专栏首页眯眯眼猫头鹰的小树杈leetcode449. Serialize and Deserialize BST

leetcode449. Serialize and Deserialize BST

题目要求

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

将二叉搜索树序列化和反序列化,序列化是指将树用字符串的形式表示,反序列化是指将字符串形式的树还原成原来的样子。

思路和代码

对于树的序列化,可以直接联想到对树的遍历。树的遍历包括前序遍历,中序遍历,后序遍历和水平遍历,并且可知前序遍历和中序遍历,或中序遍历和后序遍历可以构成一棵唯一的树。除此以外,因为这是一棵二叉搜索树,可知该树的中序遍历就是所有元素的从小到大的排列。

举个例子,假如一棵树的结构如下:

  3
 / \
2   4
 \
  1

该树的前序遍历结果为3,2,1,4,中序遍历为1,2,3,4。再仔细分析前序遍历的结果,结合二叉搜索树可知,比中间节点小的值一定位于左子树,反之一定位于右子树,即可以对前序遍历进行分割3,|2,1,|4。也就是说,我们可以只利用前序遍历,就可以区分出二叉搜索树的左子树和右子树。 代码如下:

    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        preorder(root, sb);
        return sb.toString();
    }

    public void preorder(TreeNode root, StringBuilder result) {
        if(root != null) {
            result.append(root.val);
            result.append(":");
            preorder(root.left, result);
            preorder(root.right, result);
        }
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data==null || data.isEmpty()) return null;
        String[] preorder = data.split(":");
        String[] inorder = Arrays.copyOf(preorder, preorder.length);
        Arrays.sort(inorder, new Comparator<String>(){

            @Override
            public int compare(String o1, String o2) {
                Integer i1 = Integer.valueOf(o1);
                Integer i2 = Integer.valueOf(o2);
                return i1.compareTo(i2);
            }
            
        });
        
        return build(inorder, preorder, 0, 0, inorder.length);
    }
    
    public TreeNode build(String[] inorder, String[] preorder, int inorderStart, int preorderStart, int length) {
        if(length <= 0) return null;
        TreeNode root = new TreeNode(Integer.valueOf(preorder[preorderStart]));
        for(int i = inorderStart ; i < inorderStart+length ; i++) {
            if(inorder[i].equals(preorder[preorderStart])) {
                root.left = build(inorder, preorder, inorderStart, preorderStart+1, i-inorderStart);
                root.right = build(inorder, preorder, i+1, preorderStart+i-inorderStart+1, inorderStart+length-i-1);
                break;
            }
        }
        
        return root;
    }

这里的代码是直接使用排序生成了二叉搜索树的中序遍历的结果,并利用先序遍历和中序遍历构造了一棵二叉搜索树。假如二叉搜索树的节点较多,该算法将会占用大量的额外空间。可以只用先序遍历作为构造树的输入,代码如下:

    public TreeNode deserialize(String data) {
        if (data==null) return null;
        String[] strs = data.split(":");
        Queue<Integer> q = new LinkedList<>();
        for (String e : strs) {
            q.offer(Integer.parseInt(e));
        }
        return getNode(q);
    }
    
    private TreeNode getNode(Queue<Integer> q) {
        if (q.isEmpty()) return null;
        TreeNode root = new TreeNode(q.poll());//root (5)
        Queue<Integer> samllerQueue = new LinkedList<>();
        while (!q.isEmpty() && q.peek() < root.val) {
            samllerQueue.offer(q.poll());
        }
        root.left = getNode(samllerQueue);
        root.right = getNode(q);
        return root;
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 513. Find Bottom Left Tree Value

    Given a binary tree, find the leftmost value in the last row of the tree.

    眯眯眼的猫头鹰
  • leetcode337. House Robber III

    最开始的思路我是采用自顶向下递归遍历树的形式来计算可能获得的最大收益。当前节点的情况有两种:选中或是没选中,如果选中的话,那么两个直接子节点将不可以被选中,如果...

    眯眯眼的猫头鹰
  • leetcode429. N-ary Tree Level Order Traversal

    这个和一般的水平遍历有所区别,因为它会记录每一行的水平遍历结果分别存在结果数组相应行。因此首先可以用水平遍历的通用解法,即队列的方式,进行解决:

    眯眯眼的猫头鹰
  • Shel正则表达式

    剧终
  • linux基础学习整理

    未来sky
  • 008.Linux文件目录管理命令基础

    CoderJed
  • Linux系统是否被植入木马的排查流程梳理

    在日常繁琐的运维工作中,对linux服务器进行安全检查是一个非常重要的环节。今天,分享一下如何检查linux系统是否遭受了入侵? 一、是否入侵检查 1)检查系统...

    洗尽了浮华
  • Centos7下ELK+Redis日志分析平台的集群环境部署记录

    之前的文档介绍了ELK架构的基础知识(推荐参考下http://blog.oldboyedu.com/elk/),日志集中分析系统的实施方案: - ELK+Red...

    洗尽了浮华
  • Linux开发环境第三方库规划

    让工作变得有条理,不乱糟糟,即使存在大量的第三方,也有章可循。简而言之,就是要保持目录的干净(如/usr/local目录),保持文件的干净(如profile文...

    一见
  • 附022.Kubernetes_v1.18.3高可用部署架构一

    Kubernetes的高可用主要指的是控制平面的高可用,即指多套Master节点组件和Etcd组件,工作节点通过负载均衡连接到各Master。

    木二

扫码关注云+社区

领取腾讯云代金券