如何编写此 JavaScript 代码来查找树是否是更少行的二叉搜索树?

Question

在我的Javascript课程的测验中，我们被告知要制作一个简单的树，并编写一个返回true或false的函数，无论它是否是BST。

我得到了不错的成绩，但我得到了 10 分，因为教练说"可以少 6 行完成"。

这是我所拥有的：

function node(value, left, right){
this.Value = value;
this.Left = left;
this.Right = right;
}
//this IS a BST, returns true
var head = new node(8, new node(9, null, null), new node(10, new node(9, null, null), new node(14, new node(13, null, null), null)));

function isBST(currNode){
if(currNode.Left === null && currNode.Right === null){
return true;
}
else if(currNode.Left.Value > currNode.Value || currNode.Right.Value < currNode.Value){
return false;
}
else{
if(currNode.Left === null){
return isBST(currNode.Right);
}
else if(currNode.Right === null){
return isBST(currNode.Left);
}
else{
return (isBST(currNode.Left) && isBST(currNode.Right));
}
}
}

console.log(isBST(head));

我在这里忽略了什么？也许它不应该是递归的？

Answer 1

当前函数的问题在于它不起作用。 它返回 true：

4
/ 
3   5
/ 
2  100

似乎此时所有其他答案都有相同的问题。 这是一个有效的，而且要短得多

function isBST(curNode, minval, maxval){
if (curNode == null) {
return true;
}
return (
(minval == null || minval <= curNode.Value) &&
(maxval == null || maxval >= curNode.Value) &&
isBST(curNode.Left, minval, curNode.Value) &&
isBST(curNode.Right, curNode.Value, maxval)
);
}

Answer 2

如果你的老师担心的只是行数......我会认为他们是一个糟糕的老师...

话虽如此...我并不是说你的代码是正确的，但这是你的代码减去无关的 return 语句，少了 6 行以上。

function node(value, left, right){
this.Value = value;
this.Left = left;
this.Right = right;
}
//this IS a BST, returns true
var head = new node(8, new node(9, null, null), new node(10, new node(9, null, null), new node(14, new node(13, null, null), null)));
function isBST(currNode){
if(currNode.Left === null && currNode.Right === null) return true;
if(currNode.Left.Value > currNode.Value || currNode.Right.Value < currNode.Value) return false;
if(currNode.Left === null) return isBST(currNode.Right);
if(currNode.Right === null) return isBST(currNode.Left);
return (isBST(currNode.Left) && isBST(currNode.Right));
}
console.log(isBST(head));

顺便说一句：冗长的可读代码胜过更少的行数，并且在99.99% 的时间内难以阅读。 0.01% 是当你在一个糟糕的老师的课堂上时，他更关心行数而不是实际查看你的作业。

旁白#2：长度超过~80个字符的行通常应拆分为多行以提高可读性。没有人喜欢阅读一长行代码。

编辑：对于以示例@ stanford.edu 建模的真实BST

var head = new node(5,
new node(3,
new node(1, null, null),
new node(4, null, null)
),
new node(9,
new node(6, null, null),
null
)
);