331. Verify Preorder Serialization of a Binary Tree

方法1：Stack

• 思路：
  当遍历这个序列，有以下几种情况，并且有相应几个事实：

  1. 如果是个number c -> 说明正在以c为root遍历这棵树，入栈。
  2. 如果是个#
     2.1 当stack.peek()是个数字，说明在的#是它的左null child，入栈以用来判断下一个节点是属于right subtree
     2.2 当stack.peek()是个#，说明以这两个#的parent c为root的subtree已被访问，此时可以去掉这课subtree，即出栈。
     1. 若此时栈顶为数字t，说明c是t的左child，说明左子树被访问，入栈一个#来以此判断下一个节点是属于right sub tree。
     2. 若栈顶仍然为#，说明t为节点的tree也被完全访问了，出栈，以此反复。

最后若stack只含有一个#说明是valid的序列。

方法2：In/Out Degree

• 思路：
  若将null也看做节点，那么对于每个节点，有如下的事实：
  1. 所有非null节点(除了root)，有1 indegree，2 outdegree。
  2. 所有null节点，有1 indegree，0 outdegree

那么如果diff = 所有outdegree - indegree，那么valid序列会满足：
diff始终 >= 0 且 最终 diff == 0