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、在序列串中查找“4，#，#”这样形式的串，并将其替换为“#”。也就是将二叉树中的叶子结点及其后空节点转换为空节点，直至最后整棵树只剩一个空节点。
注意：一定要注意空节点后面跟着若干空节点的情况。
public class Solution { public boolean isValidSerialization(String preorder) { if (preorder == null || preorder.length() == 0) { return false; } String[] strs = preorder.split(","); Stack<String> stack = new Stack<>(); for (String str : strs) { //注意空节点后面跟着空节点，如:1,#,#,#,# if (stack.size() == 1 && stack.peek().equals("#")) { return false; } //如果转换后与上一层节点仍然符合转换规则，则继续转换 while (str.equals("#") && stack.size() >= 2 && stack.peek().equals("#")) { stack.pop(); stack.pop(); } stack.push(str); } return (stack.size() == 1) && (stack.peek().equals("#")); } }
2、如果我们把空节点想象成叶子。那么对于每个节点的入度和出度：
（1）空节点#只提供1个入度
（2）非空节点，除根节点外，提供1个入度2个出度
（3）对于整棵树，入度等于出度
我们定义一个变量diff记录出度和入度的差，遇见空节点则diff-1，因为空节点提供一个入度，遇见非空节点先减一再加二。diff不能为负数且最后diff为0，则为合法序列。
public class Solution { public boolean isValidSerialization(String preorder) { int diff = 1;//diff = outdegree - indegree String[] strs = preorder.split(","); for (String str : strs) { if (--diff < 0) { return false; } if (!str.equals("#")) { diff += 2; } } return diff == 0; } }3、在这样的二叉树中，设度为0的节点为n0，度为1的节点为n1，度为2的节点为n2，来看一下空节点的数量和非空节点数量的关系。
空节点数：n0 * 2 + n1
非空节点数：n0+n1+n2
二者差为：n0-n2 = n2+1 – n2 = 1
所以在这颗二叉树中，空节点比非空节点多1。且容易知道合法序列的最后一个字符一定为#。
于是，遍历序列到倒数第二个字符，用count统计，遇到空节点count就减1，遇到非空节点count就加1，过程中count不能出现负数（否则说明空节点下面有非空节点，显然不对）。最后检查count是否为0且最后一个字符是否是#。
public class Solution { public boolean isValidSerialization(String preorder) { if (preorder == null || preorder.length() == 0) { return false; } int count = 0; String[] strs = preorder.split(","); for (int i = 0; i < strs.length - 1; i++) { if (strs[i].equals("#")) { count--; } else { count++; } if (count < 0) { return false; } } if (count != 0) { return false; } return strs[strs.length - 1].equals("#"); } }
