1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    private int ptr;

    public boolean verifyPreorder(int[] preorder) {
        ptr = 0;
        dfs(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
        return ptr == preorder.length;
    }

    private void dfs(int[] preorder, int low, int up) {
        if (ptr == preorder.length || preorder[ptr] < low || preorder[ptr] > up) {
            return;
        }
        int currVal = preorder[ptr++];
        dfs(preorder, low, currVal);
        dfs(preorder, currVal, up);
    }
}

这道题的思路不是很好想.

意思就是ptr指向要被安排的数字. 树中每一个位置都有自己的范围. 我们到了一个位置先看是否满足这个范围, 如果是, 那就在这里, 更新ptr的值. 然后安排后面的数字到自己的左支, 从左支回来后, 能被安排的就都安排了, 然后在走右支, 这样能被安排在右支的也结束了. 最后返回上层.

因此递归函数的作用就是把数字安排到一个位置. 最后我们要的是所有数字都有自己的位置. 也就是ptr == preorder.length.

这个想法是我们手动去判断演变出来的. 比如[5, 2, 1, 3, 6], 我们也是看5肯定是第一个, 然后看2, 看应该放哪里? 5左边可以, 然后看1, 发现2左边也行, 然后3, 发现2左边不行, 如何判断出来的? 2左边的范围是负无穷到2, 2的右边也不行, 因为2的右边是(2, 5), 因此我们往上走. 往回走就需要栈来存储. 就想到了递归, 需要知道每个位置的范围, 就想到了递归需要传入每个位置的范围.

时间复杂度: O(n)
空间复杂度: O(n)