跳转至

255. 验证二叉搜索树的前序遍历序列 🔒

题目描述

给定一个 无重复元素 的整数数组 preorder ， 如果它是以二叉搜索树的先序遍历排列 ，返回 true 。

 

示例 1：

输入: preorder = [5,2,1,3,6]
输出: true

示例 2：

输入: preorder = [5,2,6,1,3]
输出: false

 

提示:

  • 1 <= preorder.length <= 104
  • 1 <= preorder[i] <= 104
  • preorder 中 无重复元素

 

进阶：您能否使用恒定的空间复杂度来完成此题？

解法

方法一

思考

重建整棵 BST 再验证偏重。先序先访问根、再左、后右，栈中递减的是尚未转向右子树的结点。

当前值小于已弹出的下界则违反 BST；否则弹出所有小于它的栈顶作为新下界，再压入当前值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def verifyPreorder(self, preorder: List[int]) -> bool:
        stk = []
        last = -inf
        for x in preorder:
            if x < last:
                return False
            while stk and stk[-1] < x:
                last = stk.pop()
            stk.append(x)
        return True

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public boolean verifyPreorder(int[] preorder) {
        Deque<Integer> stk = new ArrayDeque<>();
        int last = Integer.MIN_VALUE;
        for (int x : preorder) {
            if (x < last) {
                return false;
            }
            while (!stk.isEmpty() && stk.peek() < x) {
                last = stk.poll();
            }
            stk.push(x);
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        stack<int> stk;
        int last = INT_MIN;
        for (int x : preorder) {
            if (x < last) return false;
            while (!stk.empty() && stk.top() < x) {
                last = stk.top();
                stk.pop();
            }
            stk.push(x);
        }
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func verifyPreorder(preorder []int) bool {
    var stk []int
    last := math.MinInt32
    for _, x := range preorder {
        if x < last {
            return false
        }
        for len(stk) > 0 && stk[len(stk)-1] < x {
            last = stk[len(stk)-1]
            stk = stk[0 : len(stk)-1]
        }
        stk = append(stk, x)
    }
    return true
}

评论