Блог

У меня есть следующая функция для обхода DFS по порядку. Я хочу, чтобы обход остановился и вернул true, если найдено соответствующее значение. Но это не работает, оно возвращает false, даже если значение находится в дереве. Что не так с этой функцией?

 inOrderDfs(node, value) {
    if (!node) {
      return;
    }
    
    if (node.left) this.inOrderDfs(node.left, value);
    if (node.value === value) return true;
    if (node.right) this.inOrderDfs(node.right, value);

    return false;
  }
  

Вы не возвращаетесь, когда выполняются эти условия, поэтому он продолжает идти ко дну и возвращает false :

 inOrderDfs(node, value) {
    if (!node) {
      return;
    }
    
    if (node.left) return this.inOrderDfs(node.left, value);
    //             ^^^^^^
    if (node.value === value) return true;
    
    if (node.right) return this.inOrderDfs(node.right, value);
    //              ^^^^^^
    return false;
  }
  

Вам нужно будет проверить значение, а затем выполнить возврат:

 inOrderDfs(node, value) {
    if (!node) {
       return;
    }
    
    if (node.left) return this.inOrderDfs(node.left, value);
   
    // Add this
    if (node.value === value) return true;
   
    if (node.right) return this.inOrderDfs(node.right, value);
}
  

Однако, если это BST, вы можете сделать:

 inOrderDfs(node, value) {
    if (!node) {
       return;
    }
    // Add this check first
    if (node.value === value) return true;

    if (node.left amp;amp; val < node.val) {
        return this.inOrderDfs(node.left, value);
    }
    else return this.inOrderDfs(node.right, value);
}