331. 验证二叉树的前序序列化

简介: 331. 验证二叉树的前序序列化

说在前面

🎈不知道大家对于算法的学习是一个怎样的心态呢?为了面试还是因为兴趣?不管是出于什么原因,算法学习需要持续保持。

题目描述

序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时,我们可以记录下这个节点的值。如果它是一个空节点,我们可以使用一个标记值记录,例如 #

例如,上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#",其中 # 代表一个空节点。

给定一串以逗号分隔的序列,验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

保证 每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#'

你可以认为输入格式总是有效的

  • 例如它永远不会包含两个连续的逗号,比如 "1,,3"

注意: 不允许重建树。

示例 1:

输入: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true

示例 2:

输入: preorder = "1,#"
输出: false

示例 3:

输入: preorder = "9,#,#,1"
输出: false

提示:

  • 1 <= preorder.length <= 10^4
  • preorder 由以逗号 “,” 分隔的 [0,100] 范围内的整数和 “#” 组成

解题思路

  • 首先,将输入的前序遍历序列化字符串 preorder 拆分成数组形式。
  • 判断如果序列化字符串只有一个元素且为"#“,则返回true;如果第一个元素就是”#",则返回false。
  • 初始化一个队列 q,将第一个元素加入队列中。
  • 遍历序列化数组的每个元素:
  • 如果队列为空,则返回false。
  • 如果当前元素为"#“,则持续弹出队列尾部的元素,直到队列非空且尾部元素为”#“为止,并将尾部元素改为”–"。
  • 如果当前元素不为"#",则将其加入队列。
  • 最终判断队列是否为空,若为空则返回true,否则返回false。

AC代码

/**
 * @param {string} preorder
 * @return {boolean}
 */
var isValidSerialization = function (preorder) {
  preorder = preorder.split(",");
  const len = preorder.length - 1;
  if (len === 0 && preorder[0] === "#") return true;
  if (preorder[0] === "#") return false;
  const q = [preorder[0]];
  for (let i = 1; i < preorder.length; i++) {
    if (q.length === 0) return false;
    if (preorder[i] === "#") {
      while (q.length && q[q.length - 1] == "--") {
        q.pop();
      }
      if (q.length) q[q.length - 1] = "--";
    } else {
      q.push(preorder[i]);
    }
  }
  return q.length === 0;
};

公众号

关注公众号『前端也能这么有趣』,获取更多有趣内容。

说在后面

🎉 这里是 JYeontu,现在是一名前端工程师,有空会刷刷算法题,平时喜欢打羽毛球 🏸 ,平时也喜欢写些东西,既为自己记录 📋,也希望可以对大家有那么一丢丢的帮助,写的不好望多多谅解 🙇,写错的地方望指出,定会认真改进 😊,偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章,有兴趣的也可以关注下。在此谢谢大家的支持,我们下文再见 🙌。

目录
相关文章
|
4天前
|
Go
golang力扣leetcode 297.二叉树的序列化与反序列化
golang力扣leetcode 297.二叉树的序列化与反序列化
25 0
|
4天前
|
Java Go 算法
Golang每日一练(leetDay0100) 二叉树序列化和反序列化
Golang每日一练(leetDay0100) 二叉树序列化和反序列化
33 0
Golang每日一练(leetDay0100) 二叉树序列化和反序列化
|
4天前
|
Go Python 算法
Python每日一练(20230412) 队列实现栈、二叉树序列化、交换链表节点
Python每日一练(20230412) 队列实现栈、二叉树序列化、交换链表节点
743 0
Python每日一练(20230412) 队列实现栈、二叉树序列化、交换链表节点
|
4天前
|
算法
剑指 Offer 37:序列化二叉树
剑指 Offer 37:序列化二叉树
21 0
|
4天前
|
存储 XML JSON
数据传输的艺术:深入探讨序列化与反序列化
数据传输的艺术:深入探讨序列化与反序列化
74 0
|
4天前
|
存储 C#
C#中的序列化和反序列化
C#中的序列化和反序列化
23 0
|
4天前
|
存储 Java 数据库
|
4天前
|
存储 安全 Java
Java一分钟之-Java序列化与反序列化
【5月更文挑战第14天】Java序列化用于将对象转换为字节流,便于存储和网络传输。实现`Serializable`接口使类可被序列化,但可能引发隐私泄露、版本兼容性和性能问题。要避免这些问题,可使用`transient`关键字、控制`serialVersionUID`及考虑使用安全的序列化库。示例代码展示了如何序列化和反序列化对象,强调了循环引用和未实现`Serializable`的错误。理解并妥善处理这些要点对优化代码至关重要。
14 1
|
4天前
|
JSON 安全 Java
Spring Boot 序列化、反序列化
本文介绍了Spring Boot中的序列化和反序列化。Java提供默认序列化机制,通过实现Serializable接口实现对象到字节流的转换。Spring Boot默认使用Jackson处理JSON,可通过注解和配置自定义规则。然而,序列化可能引发安全问题,建议使用白名单、数据校验和安全库。最佳实践包括使用标准机制、自定义规则及注意版本控制。文章还提醒关注性能并提供了相关参考资料。
67 2
|
4天前
|
XML 存储 JSON
c#XML、JSON的序列化和反序列化,看完你就懂了
c#XML、JSON的序列化和反序列化,看完你就懂了
28 0