首页 > 编程语言 >二叉树的序列化和反序列化(Java)

二叉树的序列化和反序列化(Java)

时间:2024-08-21 17:07:24浏览次数:13  
标签:node TreeNode Java 二叉树 sb return 序列化

概述

关于面试中常见的其他二叉树算法题,参考面试+算法之二叉树(Java)。二叉树的定义(注意到有使用lombok提供的两个注解):

@lombok.Data
@lombok.AllArgsConstructor
private static class TreeNode {
    private TreeNode left;
    private TreeNode right;
    private final int val;

    TreeNode(int x) {
        this.val = x;
    }
}

将有序数组转换为二叉搜索树

给定一个升序排序的整数数组nums,将其转换为一棵高度平衡的二叉搜索树。来自LeetCode

分析:给定一个有序数组,转换成二叉搜索树,即左子树小于根节点,根节点小于右子树,满足条件的二叉搜索树显然不止一种。

一般情况下,大多数人都会考虑取数组的中间元素作为根节点。为啥选择中间元素,为了确保得到的二叉树的高度差尽可能小。如果数组的元素个数是奇数,根节点可以唯一确定;如果是偶数,则根节点不唯一。所以,

如果题目没有限定高度平衡的二叉树,则得到的二叉树将会更多。最差的情况就是退化成仅有根节点和左子树或右子树的二叉树,即退化成类似链表的结构。

采用递归的方法:

public static TreeNode sortedArrayToBST(int[] nums) {
    return traversal(nums, 0, nums.length - 1);
}

private static TreeNode traversal(int[] nums, int left, int right) {
    if (left > right) {
    	// 叶子节点
        return null;
    }
    int mid = left + ((right - left) / 2);
    TreeNode node = new TreeNode(nums[mid]);
    node.left = traversal(nums, left, mid - 1);
    node.right = traversal(nums, mid + 1, right);
    return node;
}

从中序与后序遍历序列构造二叉树

来自LeetCode

public static TreeNode buildTree(int[] inOrder, int[] postOrder) {
    return helper(inOrder, postOrder, postOrder.length - 1, 0, inOrder.length - 1);
}

private static TreeNode helper(int[] inOrder, int[] postOrder, int postEnd, int inStart, int inEnd) {
    if (inStart > inEnd) {
        return null;
    }
    int currentVal = postOrder[postEnd];
    TreeNode current = new TreeNode(currentVal);
    int inIndex = 0;
    for (int i = inStart; i <= inEnd; i++) {
        if (inOrder[i] == currentVal) {
            inIndex = i;
        }
    }
    TreeNode left = helper(inOrder, postOrder, postEnd - (inEnd - inIndex) - 1, inStart, inIndex - 1);
    TreeNode right = helper(inOrder, postOrder, postEnd - 1, inIndex + 1, inEnd);
    current.left = left;
    current.right = right;
    return current;
}

序列化

递归的思想,采用前序遍历,对空节点需要特殊处理,使用任何占位符都可:

public static String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    serializeHelper(root, sb);
    return sb.substring(0, sb.length() - 1);
}

private static void serializeHelper(TreeNode node, StringBuilder sb) {
    if (node == null) {
        sb.append("#,"); // 空节点
        return;
    }
    sb.append(node.val).append(",");
    serializeHelper(node.left, sb);
    serializeHelper(node.right, sb);
}

反序列化

能否从序列化后的字符串,反序列化得到一棵树呢?
答案是可以的。前提是知道对空节点的处理(填位字符串)策略,节点的间隔(字符)策略。

能否从序列化后的字符串,反序列化得到原始的二叉树?
答案是不一定,如果想要反序列化得到原始的二叉树,有一些前提条件:

  • 序列化方案,是前序、中序还是后序
  • 对空节点的处理策略
  • 节点的间隔(字符)策略
public static TreeNode deserialize(String data) {
    LinkedList<String> nodes = new LinkedList<>(Arrays.asList(data.split(",")));
    return deserializeHelper(nodes);
}

private static TreeNode deserializeHelper(LinkedList<String> nodes) {
    String val = nodes.removeFirst();
    if (val.equals("#")) {
        return null;
    }
    TreeNode node = new TreeNode(Integer.parseInt(val));
    node.left = deserializeHelper(nodes);
    node.right = deserializeHelper(nodes);
    return node;
}

测试方法:

public static void main(String[] args) {
	TreeNode head = init();
	String s = serialize(head);
	// TreeNode.toString()方法
	String b = deserialize(s).toString();
	System.out.println("序列化:" + s);
	System.out.println("反序列化:" + b);
}

TreeNode.toString()方法:

@Override
public String toString() {
    return toString(this);
}

public String toString(TreeNode r) {
    if (r == null) {
        return "#";
    } else {
        return r.val + "," + toString(r.left) + "," + toString(r.right);
    }
}

输出:

序列化:8,4,2,#,1,#,#,3,#,#,7,#,6,5,#,#,#
反序列化:8,4,2,#,1,#,#,3,#,#,7,#,6,5,#,#,#

结论:

  • 已知序列化方案和空节点处理策略后,可唯一反序列化得到原始二叉树
  • 二叉树的打印方法里对空节点的处理策略保持一致,且间隔符都是,,则两个字符串相等

进阶

如果不知道序列化方案,如何反序列化得到二叉树?

结论:可以反序列化,但是不一定是原始的二叉树,所以这个反序列化也没有任何意义。

为了解决这个问题,有几个选择:

  • 使用包含遍历顺序信息的序列化格式:
    在序列化字符串中包含遍历顺序信息。例如,在字符串前面加上遍历顺序的标识符(如P表示前序(Pre-order),I表示中序(In-order),O表示后序(post-Order))。
  • 双序列化:
    使用两种不同的遍历顺序分别序列化树,并将两个序列化结果一起保存。两种方案字符|以分隔。例如,使用前序和中序,或后序和中序。

其中方案二基于这样一个已被证实的结论:若存在对同一棵二叉树的两种不一样的遍历(序列化)方案,则一定可以唯一确定这棵二叉树。

/**
 * 序列化二叉树(前序和中序)
 */
public static String serialize1(TreeNode root) {
    StringBuilder preOrder = new StringBuilder();
    StringBuilder inOrder = new StringBuilder();
    serializePreOrder(root, preOrder);
    serializeInOrder(root, inOrder);
    return preOrder.toString() + "|" + inOrder.toString(); // 使用 | 作为分隔符
}

private static void serializePreOrder(TreeNode node, StringBuilder sb) {
    if (node == null) {
        sb.append("#,");
        return;
    }
    sb.append(node.val).append(",");
    serializePreOrder(node.left, sb);
    serializePreOrder(node.right, sb);
}

private static void serializeInOrder(TreeNode node, StringBuilder sb) {
    if (node == null) {
        sb.append("#,");
        return;
    }
    serializeInOrder(node.left, sb);
    sb.append(node.val).append(",");
    serializeInOrder(node.right, sb);
}

/**
 * 反序列化二叉树
 */
public static TreeNode deserialize1(String data) {
    // 需预知的信息:两个字符串的分隔符
    String[] parts = data.split("\\|");
    // 需预知的信息:序列化的间隔符
    LinkedList<String> preOrderNodes = new LinkedList<>(Arrays.asList(parts[0].split(",")));
    LinkedList<String> inOrderNodes = new LinkedList<>(Arrays.asList(parts[1].split(",")));
    return buildTree(preOrderNodes, inOrderNodes);
}

private static TreeNode buildTree(LinkedList<String> preOrderNodes, LinkedList<String> inOrderNodes) {
    // 需预知的信息:对空节点的处理策略
    if (preOrderNodes.isEmpty() || preOrderNodes.peek().equals("#")) {
        preOrderNodes.poll();
        inOrderNodes.poll();
        return null;
    }
    String rootVal = preOrderNodes.poll();
    TreeNode root = new TreeNode(Integer.parseInt(rootVal));
    int inOrderIndex = inOrderNodes.indexOf(rootVal);
    root.left = buildTree(preOrderNodes, new LinkedList<>(inOrderNodes.subList(0, inOrderIndex)));
    root.right = buildTree(preOrderNodes, new LinkedList<>(inOrderNodes.subList(inOrderIndex + 1, inOrderNodes.size())));
    inOrderNodes.poll();
    return root;
}

可以看出,这两个方案还是得提前知道一些规则信息。事实上,网络通信就是一个包含序列化和反序列化的过程,如果不知道序列化规则(即协议信息),则反序列化几乎没有意义。

参考

标签:node,TreeNode,Java,二叉树,sb,return,序列化
From: https://www.cnblogs.com/johnny-wong/p/18368915

相关文章

  • 面试+算法之动态规划(Java):斐波那契、背包问题、走棋盘、分苹果、连续子数组最大和、
    概述Dynamicprogramming,简称DP,动态规划,基础算法之一,维基百科的解释:是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题,动态规划方法所耗时......
  • 面试+算法之回文(Java):验证回文串、回文数、最长回文子串、回文链表、分割成回文串、
    概述算法是一个程序员的核心竞争力,也是面试最重要的考查环节。本文整理一些与回文相关的基础算法题。注:本文语言为Java。验证回文串如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个回文串。给定一个字符......
  • 记Java使用ftp下载文件失败的坑
    使用的jar包<dependency><groupId>commons-net</groupId><artifactId>commons-net</artifactId><version>3.6</version></dependency>背景:需要从ftp服务器上拿到指定目录下的多个文件booleansuccess=ftp......
  • 二叉树入门学习 优势对比 以及 完全二叉树c++代码的实现
    二叉树介绍文档一、概述二叉树是一种常见的数据结构,它是一种树形结构,每个节点最多有两个子节点,通常称为左子节点和右子节点。二叉树的基本概念如下:节点(Node):二叉树的基本单元,包含一个值以及指向左右子节点的引用。根节点(Root):树的顶端节点,没有父节点。叶子节点(Leaf):没有子节......
  • 头歌 第4关:层次遍历二叉树
    任务描述本关任务:给定一棵二叉树,借助队列实现层次遍历二叉树。相关知识为了完成本关任务,你需要掌握:1.队列的类型定义及基本操作,2.二叉树层次遍历。队列的类型定义及基本操作队列的类型定义:#define MAXSIZE100  //最大长度typedefBiTNode*QElemType;//队列中......
  • java计算机毕业设计盐城市亭湖区药店销售管理系统(开题+程序+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着医疗卫生事业的快速发展和人们健康意识的不断提升,药品零售市场日益繁荣,盐城市亭湖区作为人口密集、经济活跃的区域,药店数量激增,市场竞争日趋激烈......
  • java计算机毕业设计婴幼儿奶粉推荐系统(开题+程序+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着婴幼儿市场的蓬勃发展,婴幼儿奶粉作为宝宝成长的重要营养来源,其选择与品质日益受到家长们的高度关注。然而,面对市场上琳琅满目的奶粉品牌与种类,如......
  • java计算机毕业设计新世纪售房管理系统(开题+程序+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景随着房地产市场的蓬勃发展,房地产销售与管理面临着前所未有的挑战与机遇。传统的手工或简单的信息化管理方式已难以满足日益增长的业务需求,特别是在客......
  • Java计算机毕业设计框架的贵州农产品销售平台设计与实现(开题+源码+论文)
    本系统(程序+源码)带文档lw万字以上 文末可获取一份本项目的java源码和数据库参考。系统程序文件列表开题报告内容研究背景在乡村振兴战略的大背景下,贵州作为农业大省,拥有丰富的农产品资源,但长期以来面临着信息不对称、销售渠道狭窄、品牌知名度不高等问题,严重制约了当地农......
  • 利用java设计模式的思维优化代码
    在Java开发中,设计模式提供了一套解决常见软件设计问题的成熟方案。通过合理应用设计模式,可以提高代码的可维护性、可读性和扩展性。以下是几个常用设计模式的示例,说明如何利用设计模式思维来优化代码。1.工厂模式(FactoryPattern)场景:假设你在开发一个系统,需要创建不同类......