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 #.
_9_
/ \
3 2
/ \ / \
4 1 # 6
/ \ / \ / \
# # # # # #
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
思路1
使用栈，每遇到有两个#连在一起的时候，就意味着有一个叶子节点检测完了，我们从栈里去掉这两个空节点和叶子节点，将这个叶子节点替换为#。
举个例子：
preorder = 1,2,3,#,#,#,#
Pass 1: stack = [1]
Pass 2: stack = [1,2]
Pass 3: stack = [1,2,3]
Pass 4: stack = [1,2,3,#]
Pass 5: stack = [1,2,3,#,#] -> stack = [1,2,#]
Pass 6: stack = [1,2,#,#] -> stack = [1,#]
Pass 7: stack = [1,#,#] -> stack = [#]
最后stack的样子应该是这样的：stack=[#]，否则就是错的。。。。
在这个过程中，有些情况直接就可以判断这个先序遍历是错的，不需要再向后遍历字符串了。
var isValidSerialization = function(preorder) {
preorder = preorder.split(',');
var num = preorder.length;
var stack = [preorder[0]];
for (var i = 1;i < num;i++) {
if (stack.length===0)
return false;
if (preorder[i]!=='#') {
stack.push(preorder[i]);
} else {
if (stack[stack.length-1]==='#') {
stack.pop();
if (stack.length===0)
return false;
stack.pop();
stack.push("#");
while (stack.length>2&&stack[stack.length-1]==='#'&&stack[stack.length-2]==='#') {
stack.pop();
stack.pop();
if (stack.length===0)
return false;
stack.pop();
stack.push("#");
}
} else {
stack.push("#");
}
}
}
if (stack.pop()!=='#')
return false;
if (stack.length!==0)
return false;
return true;
};
思路2
用图的理论来做这些。
一个根节点提供两个出度
一个非叶子节点提供一个入度两个出度
一个叶子节点提供一个入度
最后所有的出度和入度相减应该为0
我们设diff=出度-入度
然后每遍历一个节点，减掉一个入度，如果这个节点不是叶子节点我们再加上两个出度
由于根节点有一点特殊，比起其他非叶子节点，它不提供一个入度，所以我们初始化diff为1来抵消这一点。
由于是先序遍历，diff永远不可能小于0。
var isValidSerialization = function(preorder) {
preorder = preorder.split(',');
var diff = 1;
for (var i = 0;i < preorder.length;i++) {
diff--;
if (diff<0)
return false;
if (preorder[i]!=='#')
diff += 2;
}
return diff===0;
};
这个算法虽然简单，但是极大的可能需要遍历整个字符串才能得到结果。
