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

[Rain120]

题目

给定一个整数数组，你需要验证它是否是一个二叉搜索树正确的先序遍历序列。

你可以假定该序列中的数都是不相同的。

参考以下这颗二叉搜索树：

     5
    / \
   2   6
  / \
 1   3

示例 1： 输入: [5,2,6,1,3] 输出: false

示例 2： 输入: [5,2,1,3,6] 输出: true

[Rain120]

var verifyPreorder = function(preorder) {
  const queue = [];
  let left = -Infinity;

  for (const cur of nums) {
    // 小于 cur 的则可以判断为当前子树左子树节点和根节点
    // 将其弹出，left 应该为当前数组的最小值
    while (queue.length && queue[0] < cur) {
      left = queue.shift();
    }

    // left 大于 cur 时为左子树节点大于右子树节点的情况，
    // 不满足二叉搜索树的特点，所以应该为 false
    if (left > cur) {
      return false;
    }

    queue.unshift(cur);
  }

  return true;
};