如何编写此JavaScript代码以查找树是否是更少行中的二叉搜索树？ [英] How to write this JavaScript code for finding if a tree is a Binary Search Tree in fewer lines?

问题描述

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

In a quiz for my Javascript class, we were told to make a simple tree and write a function that returns true or false whether it is a BST or not.

我得到了一个不错的成绩，但我得到了10分，因为教练说它可以在6行中完成。

I got a decent grade, but i got 10 points off because the instructor said "It can be done in 6 less lines".

这就是我所拥有的：

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

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

Anything I'm overlooking here? Maybe it shouldn't have been recursive?

推荐答案

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

The problem with your current function is that it does not work. It returns true for:

     4
    / \
   3   5
  / \
 2  100

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

It seems that all the other answers at this time have the same problem. Here's one that works and is a lot shorter

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

这篇关于如何编写此JavaScript代码以查找树是否是更少行中的二叉搜索树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！