Leetcode Problem 331: Verify Pre

要求在不重建树的情况下，判断一个字符串是否为某树的先序遍历序列。

使用递归求解。

若一个序列只有一个“#“，显然这是正确的。

若一个序列的第一个元素不是"#"，那么一个合法的序列一定可以分成三部分来看待：根（第一个元素），左子树（从第二个元素开始算起到第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;
    }
}