初学python记录：力扣331. 验证二叉树的前序序列化

最新推荐文章于 2025-06-03 18:15:13 发布

鱼翅睡大觉

最新推荐文章于 2025-06-03 18:15:13 发布

阅读量229

点赞数 4

文章标签： leetcode 数据结构算法

本文链接：https://blog.csdn.net/Demo0219/article/details/137208224

版权

题目：

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

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

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

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

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

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

注意：不允许重建树。

思考：

1. 用“#”表示空节点，那么所有值不为“#”的节点都有两个子节点 ----> 用一个数据结构记录每个节点的两个子节点空位是否被填充

2. 前序遍历二叉树 ----> 先进后出 ----> 栈

代码如下：

class Solution(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        nodes = preorder.split(',')    # 按逗号分割字符串
        stack = [1]     # 用栈存储节点的子节点左右槽位，初始化
        for node in nodes:
            if not stack:    # 若栈空，即还有节点没有填充，但已经没有槽位，返回False
                return False  

            stack[-1] -= 1     # 否则填充节点，将栈顶槽位减一
            if stack[-1] == 0:     # 若栈顶为0，即该节点槽位已满
                stack.pop()

            if node != '#':    
                # 对于普通节点，增加一个值为2的槽位
                stack.append(2)

        if not stack:     # 栈空说明整棵树填充满了，证明是二叉树
            return True  
        else:
            return False

提交通过：