题目要求
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:
Input: “9,3,4,#,#,1,#,#,2,#,6,#,#”
Output: true
Example 2:
Input: “1,#”
Output: false
Example 3:
Input: “9,#,#,1”
Output: false
思路和代码
我们知道，任何两个节点都可以和位于左边的非叶节点构成一棵有三个节点的树。如果我们从右往左看先序遍历，就知道后两个节点如果遇到第三个节点，则该节点就应当是这两个节点的父节点。我们可以将每一个 #看做一个根节点，每遇到# 就将记录的根节点数加一，当遇到数字时，则代表该数字应当能够和两个节点构成新的树，并且该数字成为新的根节点，因此需要将根节点数量减一。如果在遍历的过程中根节点数量小于 1，则说明这棵树有问题。而如果遍历结束之后，剩下的根节点数不等于 1，也说明这个先序遍历存在问题。
public boolean isValidSerialization(String preorder) {
if(preorder==null) return false;
if(preorder.length() == 0) return true;
String[] nodes = preorder.split(“,”);
int nodeCount = 0;
for(int i = nodes.length – 1; i >= 0 ; i–) {
if(nodes[i].equals(“#”)) {
nodeCount++;
} else {
nodeCount–;
}
if(nodeCount <= 0) return false;
}
return nodeCount == 1;
}