Readme

331.Verify-Preorder-Serialization-of-a-Binary-Tree

此题用到了这么一个性质：对于满二叉树，所有节点的入度和出度之差为0.

关于入度和出度，我们知道，根节点的净值是-2（两个出度），非叶子节点的净值是-1（一个入度两个出度），叶子节点的净值是1（一个入度零个出度）。在对先序遍历的过程中，我们只能区分叶子和非叶子节点，但是无法再细分是否是根节点。不过因为根节点只有一个，所以我们如果把根节点也当做一般的非叶子节点来处理的话，遍历所有节点之后的总净值应该是1。也就是说，如果我们按先序遍历所有节点，遇到非#节点就减一，遇到#节点就加一，最终的结果必须是1。

此外还有另外一个判定条件。在先序遍历的过程中，总有一些子二叉树是没有被完全遍历完的，也就是说，对于这些子二叉树，已经遍历的非叶子节点总比已经遍历的叶子节点多。所以按照上述的规则，遍历的过程中(不包括最后一个节点)，总净值不能大于0。注意，一旦把最后一个节点遍历完毕，根据上一个结论，总净值必须是1。

Leetcode Link