用于预购遍历检查的Javascript等效代码

Question

我想知道如何为Javascript编写用Java编写的预购遍历代码？

首先，我正在为极客练习这个问题：

检查给定数组是否可以表示二进制搜索树的预购遍历

为此，他们写了这个算法

1) Create an empty stack.
2) Initialize root as INT_MIN.
3) Do following for every element pre[i]
a) If pre[i] is smaller than current root, return false.
b) Keep removing elements from stack while pre[i] is greater
then stack top. Make the last removed item as new root (to
be compared next).
At this point, pre[i] is greater than the removed root
(That is why if we see a smaller element in step a), we 
return false)
c) push pre[i] to stack (All elements in stack are in decreasing
order) 

我无法理解上面的算法，因为我不确定什么是空堆栈(可能是空数组？(，INT_MIN？

如果空堆栈是一个空数组，那么这个语句意味着什么

Keep removing elements from stack while pre[i] is greater
then stack top. Make the last removed item as new root (to
be compared next).

简而言之，我能够制定algo，有其他语言编写的algo，但我只知道如何用Javascript编写代码。

你能帮我让上面代码的算法更可读吗？

Answer 1

回答您的问题：

1. 作者所说的INT_MIN是指尽可能小的整数(数(，因此任何其他数都将大于INT_MIN。对于Javascript，您可以使用-Infinity，它将比任何其他数字都小，以便进行比较。您不能对-Infinity执行数学运算，但在这种情况下不需要
2. 堆栈是一种数据结构(类似于数组的特殊情况(，它允许您将元素叠加到堆栈中，然后从堆栈中弹出，返回最新添加的元素。如果你想在JS中有堆栈，你可以选择1。在数组上创建一个包装器，添加.push、.pop、.peek方法或2。只需使用数组并将其视为堆栈即可。在这种情况下做后者更容易
3. If empty stack as an empty array, then what does this statement mean?一开始它是空的，但当你浏览这个例子时，你会看到一些项仍然被添加到堆栈中，当你进入这个语句时，会检查堆栈是否为空

。

const canRepresentBST = (pre) => {
const stack = []
let root = -Infinity
for (let i = 0; i < pre.length; i++) {
if (pre[i] < root) {
return false
}
while (stack.length && stack[stack.length - 1] < pre[i]) {
root = stack.pop()
}
stack.push(pre[i])
}
return true
}
const pre1 = [40,30,35,80,100]
console.log(canRepresentBST(pre1))
const pre2 = [40,30,35,20,80,100]
console.log(canRepresentBST(pre2))

该算法的目的是确定给定的数字数组(pre(是否是二进制搜索树的有效预序遍历

Answer 2

应该就是这样了。我从您的示例中提取了java代码，并将其转换为js。

const canRepresentBST = (pre) => {
let root = Number.MIN_SAFE_INTEGER
let s =  []
for (let i = 0; i < pre.length; i++) { 
if (pre[i] < root) { 
return false 
} 
while (s.length > 0 && s[s.length-1] < pre[i]) { 
root = s.pop()  
} 
s.push(pre[i]) 
} 
return true 
} 
let pre1 = [40, 30, 35, 80, 100]
let pre2 = [40, 30, 35, 20, 80, 100]
console.log(canRepresentBST(pre1) ? 'true' : 'false')
console.log(canRepresentBST(pre2) ? 'true' : 'false')