Java序列化二叉树

文章目录

一、题目解析

请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，我们可以把一个只有根节点为1的二叉树序列化为"1,"，然后通过自己的函数来解析回这个二叉树

序列化和反序列化可以借助层序遍历实现，利用队列的先进先出特性

序列化：利用队列实现层序遍历

反序列化：利用层序遍历的特点，i 节点的左右节点为 i+1，i+2

二、代码

public class Test_18 { String Serialize(TreeNode root) { StringBuffer buffer = new StringBuffer(); Queue<TreeNode> queue = new LinkedList<>(); if (root == null) { return "#,"; } queue.add(root); //队列不空，逐次添加左右子树 while (!queue.isEmpty()){ TreeNode node = queue.poll(); if (node != null) { queue.add(node.left); queue.add(node.right); buffer.append(node.val+","); }else { buffer.append("#"+","); } } return buffer.toString(); } TreeNode Deserialize(String str) { if (str == null || str.length() == 0) { return null; } //以逗号进行分割，获取二叉树值列表 String[] split = str.split(","); //用来构建二叉树 TreeNode[] nodes = new TreeNode[split.length]; for (int i = 0; i < split.length; i++) { if (!split[i].equals("#")){ //初始化node[i]节点，并为其赋值 nodes[i]=new TreeNode(Integer.valueOf(split[i])); } } //利用层序遍历的特点，对于节点 i 它的左右节点分别为：i+1,i+2 for (int i = 0,j=1; j < nodes.length; i++) { if (nodes[i] != null) { nodes[i].left=nodes[j++]; nodes[i].right=nodes[j++]; } } return nodes[0]; } } 

三、总结

（1）String、StringBuffer 和 StringBuilder 的区别

（2）字符的分割函数 split：将字符串以指定字符分割

 //以逗号进行分割，获取二叉树值列表 String[] split = str.split(","); 

import java.util.LinkedList; import java.util.Queue; /**
 * @Author: Yolo
 * @Date: 2020/9/28 20:14
 * @Description:
 */ public class Test_18 { String Serialize(TreeNode root) { StringBuilder buffer = new StringBuilder(); Queue<TreeNode> queue = new LinkedList<>(); if (root == null) { return "#,"; } queue.add(root); //队列不空，逐次添加左右子树 while (!queue.isEmpty()){ TreeNode node = queue.poll(); if (node != null) { queue.add(node.left); queue.add(node.right); buffer.append(node.val+","); }else { buffer.append("#"+","); } } return buffer.toString(); } TreeNode Deserialize(String str) { if (str == null || str.length() == 0) { return null; } //以逗号进行分割，获取二叉树值列表 String[] split = str.split(","); //用来构建二叉树 TreeNode[] nodes = new TreeNode[split.length]; for (int i = 0; i < split.length; i++) { if (!split[i].equals("#")){ //初始化node[i]节点，并为其赋值 nodes[i]=new TreeNode(Integer.valueOf(split[i])); } } //利用层序遍历的特点，对于节点 i 它的左右节点分别为：i+1,i+2 for (int i = 0,j=1; j < nodes.length; i++) { if (nodes[i] != null) { nodes[i].left=nodes[j++]; nodes[i].right=nodes[j++]; } } return nodes[0]; } } 

本文地址：https://blog.csdn.net/nanhuaibeian/article/details/108853402