序列化和反序列化二叉搜索树【LC449】
序列化是将数据结构或对象转换为一系列位的过程,以便它可以存储在文件或内存缓冲区中,或通过网络连接链路传输,以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串,并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。
BFS
-
思路文章来源:https://www.toymoban.com/news/detail-694398.html
- 序列化:按照层序遍历序列化二叉搜索树,每个值以","分隔,不记录null值
- 反序列化:由于该树为二叉搜索树,满足左子树值小于根、右子树值大于根;因此对于每个节点
i
i
i,可以从根出发,找到相应的插入位置,将当前节点记为
cur
,插入节点值记为 x x x- 如果当前节点的左子节点为空,并且 c u r . v a l > x cur.val > x cur.val>x,那么插入位置为 c u r . l e f t cur.left cur.left
- 如果当前节点的右子节点为空,并且 c u r . v a l < x cur.val < x cur.val<x,那么插入位置为 c u r . r i g h t cur.right cur.right
- 都不满足时,选择向左或者向右遍历
-
实现文章来源地址https://www.toymoban.com/news/detail-694398.html
//@背书包的小白熊 public class Codec { // Encodes a tree to a single string. //java广度优先搜索层序遍历,记录所有节点的val值,用逗号隔开 public String serialize(TreeNode root) { if (root == null) return ""; Queue<TreeNode> queue = new LinkedList(); queue.offer(root); StringBuilder sb = new StringBuilder(); while (!queue.isEmpty()) { TreeNode cur = queue.poll(); sb.append(cur.val).append(","); if (cur.left != null) queue.offer(cur.left); if (cur.right != null) queue.offer(cur.right); } return sb.deleteCharAt(sb.length() - 1).toString(); } // Decodes your encoded data to tree. //将字符串恢复成树 public TreeNode deserialize(String data) { if (data.equals("")) return null; //将data分隔开 String[] arr = data.split(","); //初始化根节点 TreeNode root = new TreeNode(Integer.valueOf(arr[0])); //从第二个节点开始循环,二叉搜索树的特点是: //1.非空左子树的所有键值小于其根结点的键值。 //2.非空右子树的所有键值大于其根结点的键值。 //3.左、右子树都是二叉搜索树。 //利用此性质,每次搜索插入节点时间复杂度为O(logn),总体时间复杂度为O(nlogn) for (int i = 1; i < arr.length; i++) { int x = Integer.valueOf(arr[i]); TreeNode cur = root; while (cur != null) { //如果左子树为空,并且x < cur.val 证明此节点就是需要插入的节点位置 if (cur.left == null && x < cur.val) { cur.left = new TreeNode(x); break; //如果右子树为空,并且x > cur.val 证明此节点就是需要插入的节点位置 } else if (cur.right == null && x > cur.val) { cur.right = new TreeNode(x); break; } //选择向左或向右遍历 if (x < cur.val) cur = cur.left; else cur = cur.right; } } return root; } }
- 复杂度
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( n log n ) O(n \log n) O(nlogn)
- 复杂度
到了这里,关于【每日一题Day316】LC449序列化和反序列化二叉搜索树 | BFS的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!