要求在不重建树的情况下，判断一个字符串是否为某树的先序遍历序列。
使用递归求解。
若一个序列只有一个“#“，显然这是正确的。
若一个序列的第一个元素不是"#"，那么一个合法的序列一定可以分成三部分来看待：根（第一个元素），左子树（从第二个元素开始算起到第x个元素），右子树（从第x+1个元素算起到序列末尾）。因此，跳过第一个元素（根）后，我们在从第二个元素开始的子序列中，先尝试找到一棵完整的树（左子树），如果找不到，那么显然是不合法的。如果找到了，那么我们再从这棵完整的树后面开始，尝试找另一棵树（右子树），如果找不到，那么显然是不合法的。
从第一个元素开始，如果找到了一个完整的树，且长度和序列长度一致，那么就是合法的，否则就是非法的。
空间复杂度：O(1)（注意，为了简便，我下面的代码因为用了一个数组放置从字符串中分离出来的序列，事实上是O(n)，但其实这是可以省略的，并非算法本质）
时间复杂度：O(n)
代码如下：
public class Solution {
public boolean isValidSerialization(String preorder) {
String[] x = preorder.split(",");
if (findTree(x, 0) == x.length) {
return true;
}
return false;
}
private int findTree(String[] preorder, int start) {
if (preorder.length - start == 0) {
return -1;
}
if (preorder[start].equals("#")) {
return start + 1;
}
int left = findTree(preorder, start + 1);
if (left < 0) {
return -1;
}
int right = findTree(preorder, left);
if (right < 0) {
return -1;
}
return right;
}
}
