跳转至

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

1、题目描述

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

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

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

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

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

你可以认为输入格式总是有效的,例如它永远不会包含两个连续的逗号,比如 "1,,3"

示例 1:

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

示例 2:

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

示例 3:

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

2、解题思路

​ 根据题目,首先,#号的数量肯定是数字数目加一

​ 从上到下,进来的看做入,下方的看做出,整棵树入和出应该是相同的

​ 换一个角度来说,对一个数字节点来讲,他可以匹配两个"#",也可以匹配一个数字一个"#"

​ 因此,前序遍历的过程中,进来的始终要大于出去的,最后一个节点也肯定是"#"

  • 初始化一个计数器,如果当前节点是数字,表示下方能够匹配2个"#",但是他也占用了一个"#"的名额,所以,增加一个"#"计数

假如是一颗空树,默认是需要一个"#",也就是说,我们在根节点前方假设是空的,放了一个#

然后根据上面的规则,开始判断

class Solution:
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        temp = preorder.split(',')

        count = 1

        for node in temp:
            count -= 1
            if count < 0:
                return False

            if node != "#":
                count += 2

        if count == 0:
            return True

        return False