One way to serialize a binary tree is to use PRe-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #.

For example, the above binary tree can be serialized to the string “9,3,4,#,#,1,#,#,2,#,6,#,#”, where # represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character ‘#’ representing null pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as “1,,3”.

Example 1: “9,3,4,#,#,1,#,#,2,#,6,#,#” Return true

Example 2: “1,#” Return false

Example 3: “9,#,#,1” Return false

s思路: 1. 判斷樹的表示方法是否有效，而且不讓構造樹。 2. 先看用iterative的方法，用stack就可以搞定，例如：”9,3,4,#,#,1,#,#,2,#,6,#,#”，碰到數就直接push到stack,碰到#，則討論一下，當第一次遇到#也直接push，第二次遇到#則把之前的＃pop，還要把#前的數pop，然后再放入#.注意的是，每次放入的時候，都要檢查stack頂上是否有#,如果有，就要pop兩次再看是否有#,直到前面是數或stack為空為止！ 3. 參考https://discuss.leetcode.com/topic/45326/c-4ms-solution-o-1-space-o-n-time/2　真是妙不可言！思考自己上面的思路，討論的情況很是比較多，雖然做法中規中矩，但是如果足夠敏銳的話，就可以想到這種做法太focus到細節上了，應該比較top-down的解法。比如上面的參考。思路是這樣的，實時統計樹的容量capacity，初始化capacity=1,表示根節點，然后遍歷的時候，只需找’,’，因為＃就在“，”之前，而且我們只關注是否是#,如果不是＃，表示一個新節點，那么capacity就增加兩個，而且每次遍歷一個節點時，就capacity–用來表示由于遇到一個節點，容量減少！如果在某個時候，容量<0,則表示不能構造樹了。最后容量等于０，表示剛剛裝滿，因此可以構造樹！ 4. 這個統計數據結構的某個參量的做法，確實很贊，想到在圖的遍歷中，如果用bfs，也可以來統計入度，出度這些參量。你看，這里面也一樣是，需要統計樹的一個參量！方法很特殊，不過值得推廣，統計數據結構的某一個參量！