Verify Preorder Sequence in Binary Search Tree

Description

null

Solution(javascript)

// /**
//  * 先递减然后递增？ 不行，比如[1,3,2]
//  * @param {number[]} preorder
//  * @return {boolean}
//  */
// const verifyPreorder = function (preorder) {
//   let increasing = false
//   for (let i = 1; i < preorder.length; i++) {
//     if (preorder[i] > preorder[i - 1]) {
//       increasing = true
//       continue
//     }
//     if (increasing === true && preorder[i] < preorder[i - 1]) {
//       return false
//     }
//   }
//   return true
// }


// /** 1: recursion O(n^2)
//  * @param {number[]} preorder
//  * @return {boolean}
//  */
// const verifyPreorder = function (preorder) {
//   const aux = (left, right) => {
//     if (left >= right) {
//       return true
//     }
//     const root = preorder[left]
//     let index = right + 1
//     for (let i = left + 1; i <= right; i++) {
//       if (preorder[i] > root) {
//         index = i
//         break
//       }
//     }
//     let leftMax = -Infinity
//     for (let i = left + 1; i < index; i++) {
//       leftMax = Math.max(leftMax, preorder[i])
//     }
//     let rightMin = Infinity
//     for (let i = index; i <= right; i++) {
//       rightMin = Math.min(rightMin, preorder[i])
//     }
//     if (root <= leftMax || root >= rightMin) {
//       return false
//     }
//     return aux(left + 1, index - 1) && aux(index, right)
//   }
//   return aux(0, preorder.length - 1)
// }


/** 2: Stack O(n)
 * @param {number[]} preorder
 * @return {boolean}
 */
const verifyPreorder = function (preorder) {
  const stack = []
  let min = -Infinity
  for (const num of preorder) {
    if (num <= min) {
      return false
    }
    while (stack.length && num > stack[stack.length - 1]) {
      min = stack.pop()
    }
    stack.push(num)
  }
  return true
}