关于BST JS递归函数执行的问题

Question

我想出了一个BST验证问题的解决方案。我会先列出问题和我写的代码，然后告诉你我不理解执行的哪一部分。

// --- Directions
/* Given a node, validate the binary search tree,
ensuring that every node's left hand child is
less than the parent node's value, and that
every node's right hand child is greater than
the parent. e.g.:

10
5   15
0     20 
999    
*/
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
insert(data) {
if (data < this.data && this.left) {
this.left.insert(data);
} else if (data < this.data) {
this.left = new Node(data);
} else if (data > this.data && this.right) {
this.right.insert(data);
} else if (data > this.data) {
this.right = new Node(data);
}
}
}
function validate(node, min = null, max = null) {
if (node.right) {
min = node.data;
if (node.right && node.right.data > min) {
return validate(node.right, min, max);
} else if (node.right && node.right.data < min) {
return false;
}
}
if (node.left) {
max = node.data;
if (node.left && node.left.data < max) {
return validate(node.left, min, max);
} else if (node.left && node.left.data > max) {
return false;
}
}
return true;
}
const n = new Node(10);
n.insert(5);
n.insert(15);
n.insert(0);
n.insert(20);
n.left.left.left = new Node(999);
console.log(validate(n));

我所期望的是，该函数将首先验证树的右侧，然后开始在左侧工作。然而，一旦它检查了右侧，它就会从递归调用中返回true。它返回到n的初始值，但不检查树左侧的第二个if语句，它只是退出函数。

我假设它可能会退出，因为最初的函数调用在第一个if语句上递归后最终返回true，所以它就不用检查第二个了。如果是这样的话，有没有办法让函数也检查第二个If语句，而不是在第一个语句之后退出函数？

Answer 1

事实上，代码的第一部分(如果node.right是真的(将始终执行return，因此不可能同时执行代码的第二部分。

当结果为false时返回是可以的，但在另一种情况下，您应该而不是返回：

function validate(node, min = null, max = null) {
if (node.right) {
min = node.data;
if (node.right && node.right.data > min) {
if (!validate(node.right, min, max)) return false; // <---
} else if (node.right && node.right.data < min) {
return false;
}
}
if (node.left) {
max = node.data;
if (node.left && node.left.data < max) {
return validate(node.left, min, max);
} else if (node.left && node.left.data > max) {
return false;
}
}
return true;
}

我只是修改了您的问题所必需的内容，但您的代码中有很多检查重复了已经断言的内容。例如，当您在第一个if块中时，不需要再次检查node.right是否正确。所以你可以将代码简化为：

function validate(node, min = null, max = null) {
if (node.right && (node.right.data < node.data || 
!validate(node.right, node.data, max))) return false;
if (node.left && (node.left.data > node.data ||
!validate(node.left, min, node.data))) return false;
return true;
}

这可能会更简化为一个退货声明，但我会留给你，-(