Question

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

English Version

题目描述

给定一个 无重复元素 的整数数组 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 中 无重复元素

 

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

解法

方法一

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

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;
  }
}

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;
  }
};

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
}