leetcode [331] 验证二叉树的前序序列化

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

     _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

题解：

第一种使用前序序列构造二叉树：

注意函数的递归终止条件

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        preorder = preorder.split(",")
        i = 0
        self.res = True
        def helper():
            nonlocal i
            if i >= len(preorder):
                self.res = False
                return 
            tmp = preorder[i]
            i += 1
            if tmp == "#":
                return 
            helper()
            helper()
        helper()
        return i == len(preorder) and self.res

第二种用栈模拟前序遍历递归建树的过程，注意使用#的循环条件

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        preorder = preorder.split(",")
        stack = []
        for item in preorder:
            while stack and stack[-1] == "#" and item == "#":
                stack.pop()
                if not stack:return False
                stack.pop()
            stack.append(item)
        return len(stack) == 1 and stack[0] == "#"

第三种是边的个数，每个非空节点总能创造出两个边，任何节点都非消耗一个边个数：

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        preorder = preorder.split(",")
        edges = 1
        for item in preorder:
            edges -= 1
            if edges < 0: return False
            if item != "#":
                edges += 2
        return edges == 0