331 验证二叉树的前序序列化-中等

题目：

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

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

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

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

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

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

注意：不允许重建树。

分析：

算法1：

还是用递归的思想，只要满足 数字,#,#这样的模式，那么就是合法的二叉树。那么是从底部向上分析还是从顶向下分析呢？很显然需要从底向上，因为只要叶子节点满足 数字,#,# 的模式，进而将其替换为 # ，继续判断其父结点。

所以这里需要用到栈结构，从左到右依次入栈，当栈顶的三个元素满足 数字,#,# 模式时，继续判断。最后栈中应该只剩下一个 #，那么就是一个合法的二叉树。

// date 2022/10/24
func isValidSerialization(preorder string) bool {
    stack := make([]string, 0, 16)
    parts := strings.Split(preorder, ",")
    for _, v := range parts {
        stack = append(stack, v)
        for len(stack) >= 3 && stack[len(stack)-1] == "#" && stack[len(stack)-2] == "#" && stack[len(stack)-3] != "#" {
            stack = stack[:len(stack)-3]
            stack = append(stack, "#")
        }
    }
    return len(stack) == 1 && stack[0] == "#"
}

算法2：【推荐该算法】

从出度和入度的角度重新理解树。

我们知道对于一个二叉树，所有节点的入度之和等于其出度之和。那么我们就可以根据这个条件进行有效判断。

对于二叉树，我们将空节点也是为叶子节点（即题目中的 #），那么则有：

1. 所有的非空节点，提供2个出度，1个入度（根节点除外）

2. 所有的空节点，提供0个出度，1个入度

我们在遍历的时候，可以计算出度与入度之差diff = outdegree - indegree。我们从根开始遍历，当一个节点出现的时候 diff-1，因为它提供一个入度；当节点不是空节点的时候 diff+2，因为非空节点提供2个出度。

如果序列式是合法的，那么整个遍历过程中 diff >= 0，并且最后的结果为零。

这里解释为为什么 diff 初始化为1，因为根节点没有父结点，所以根节点提供2个出度，0个入度。在整个遍历过程中都是先减一，如果是非空节点再加二。所以初始化为1，保证了根节点先减去1个入度，再加上2个出度，正好为2，类似链表中 伪头节点 的做法。

// date 2022/10/24
func isValidSerialization(preorder string) bool {
    // diff = outdegree - indegree
    diff := 1
    parts := strings.Split(preorder, ",")
    for _, v := range parts {
        diff -= 1
        if diff < 0 {
            return false
        }
        if v != "#" {
            diff += 2
        }
    }
    return diff == 0
}