跳到主要内容

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

链接：331.验证二叉树的前序序列化
难度：Medium
标签：栈、树、字符串、二叉树
简介：验证二叉树的前序序列化。

题解 1 - typescript​

  • 编辑时间：2021-03-12
  • 执行用时：88ms
  • 内存消耗：39.6MB
  • 编程语言：typescript
  • 解法介绍：计算深度。
function isValidSerialization(preorder: string): boolean {
  let degree = 1;
  for (const char of preorder.split(',')) {
    if (!degree) return false;
    char === '#' ? degree-- : degree++;
  }
  return degree === 0;
}

题解 2 - typescript​

  • 编辑时间：2021-03-19
  • 执行用时：100ms
  • 内存消耗：39.3MB
  • 编程语言：typescript
  • 解法介绍：逐级替换叶子节点。
function isValidSerialization(preorder: string): boolean {
  const leafReg = /d+,#,#/g;
  while (leafReg.test(preorder)) preorder = preorder.replace(leafReg, '#');
  return preorder === '#';
}

题解 3 - python​

  • 编辑时间：2024-03-31
  • 执行用时：40ms
  • 内存消耗：16.61MB
  • 编程语言：python
  • 解法介绍：dfs，对每一个节点遍历左右子节点看是否匹配。
class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        preorder = preorder.split(',')
        def dfs(idx: int) -> int:
            if idx == -1: return idx
            if idx >= len(preorder): return -1
            if preorder[idx] == '#': return idx + 1
            return dfs(dfs(idx + 1))
        return dfs(0) >= len(preorder)