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

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

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

Answer 1

事实上，你的代码的第一部分（如果 node.right 是真实的）将总是执行一个 return，所以没有办法您的代码的第二部分也会被执行。

当结果是false时return是可以的，但在其他情况下，你应该而不是return：

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

...这甚至可以减少到只有一个 return 语句，但我会留给你，-)

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

Question about the execution of a BST JS recursive function

javascript

validation

recursion

binary-search-tree

binary-search