【一天一道Leetcode】验证二叉树的前序序列化

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

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

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

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

节点1的出度为2，入度为0
节点2，5的出度为2，入度为1
节点3，4，6，7的出度为2，入度为1
空节点#的出度为0，入度为1
所有节点的出度和为14
所有节点的入度和为14

我们只要把字符串利用遍历的方式，遍历一次，
计算每个节点的出度和入度之差diff，
即diff=出度-入度

在遍历到任何一个节点的时候，

要求diff>=0,原因是还没遍历到该节点的子节点，
所以此时的出度应该大于等于入度。

如果diff<0，则代表出度<入度。此时二叉树不成立，返回False

class Solution(object):
    def isValidSerialization(self, preorder):
        nodes = preorder.split(',')
        diff = 1
        for node in nodes:
            diff -= 1
            if diff < 0:
                return False
            if node != '#':
                diff += 2
        return diff == 0

因为，我们加入一个非空节点时，
都会先减去一个入度，再加上两个出度。

但是由于根节点没有父节点，所以其入度为 0，出度为 2。

因此 diff 初始化为 1，
是为了在加入根节点的时候，
先减去一个入度，再加上两个出度，此时 diff 正好应该是2.