How to write this JavaScript code for finding if a

问题:

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.

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

This is what I had:

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?

回答1:

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

回答2:

If all your teacher is worried about is line count... I would consider them to be a bad teacher...

That being said... I'm not saying your code is correct, but here is your code minus the extraneous return statement, with more than 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;
    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));

As an aside: verbose readable code trumps less lines and hard to read 99.99% of the time. 0.01% is when you're in a bad teacher's class who cares more about line count than actually looking at your assignment.

Aside #2: A line more than ~80 characters in length should normally be split into multiple lines for readability. No one likes to read one long line of code.

EDIT: For a real BST modeled after the example @ stanford.edu

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