LeetCode 331 [Verify Preorder Serialization of a Binary Tree]

原题

先序遍历是序列化二叉树的方式之一。当遇到非空节点时，记录节点的值。如果是空节点，我们将其记为#。

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

例如，题目描述中的样例二叉树可以序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中#代表空节点。

给定一个逗号分隔值字符串，校验其是否是一个正确的二叉树先序遍历序列化字符串。设计一个不需要重建树的算法。

每一个逗号分隔值字符串中的值或者是整数，或者是字符'#'，代表空节点。

你可以假设输入格式总是有效的，例如，不可能出现两个连续的逗号，比如"1,,3"。

例1：
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true

例2：
"1,#"
Return false

例3：
"9,#,#,1"
Return false

解题思路

• 方法一：利用Stack, 把序列化的结果不断压入栈，但栈内元素大于等于3的时候，如果遇到x # # => #，此过程相当于在逐步砍掉叶节点，过程如下

      8            8          #
     / \          / \   
    9   #   =>   #   #  =>   
   / \
#   #

• 方法二：统计树的出度（out-degree）和入度（in-degree）
• 根节点提供2个出度和0个入度（但初始时diff=1）
• 所有的非空节点提供2个出度和1个入度
• 所有的空节点但提供0个出度和1个入度
• 当遍历节点时，每次diff - 1（因为节点提供了一个入度）。
• 如果节点非#，diff + 2（因为非空节点提供了2个出度）
• 如果序列化是正确的，那么diff在任何时刻都不会小于0，并且最终结果等于0

完整代码

# method 1
class Solution(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        stack = []
        for node in preorder.split(","):
            stack.append(node)
            while len(stack) >= 3 and stack[-1] == stack[-2] == "#" and stack[-3] != "#":
                stack = stack[:-3] +['#']
        return len(stack) == 1 and stack[-1] == "#"

# method 2
class Solution(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        diff = 1
        for node in preorder.split(","):
            diff -= 1
            if diff < 0:
                return False
            if node != "#":
                diff += 2
        if diff == 0:
            return True
        return False