#javascript #depth-first-search #traversal
#javascript #поиск по глубине #обход
Вопрос:
У меня есть следующая функция для обхода 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;
}
Ответ №1:
Вы не возвращаетесь, когда выполняются эти условия, поэтому он продолжает идти ко дну и возвращает 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;
}
Комментарии:
1. Я вижу, но это по-прежнему возвращает false для значений в дереве?
Ответ №2:
Вам нужно будет проверить значение, а затем выполнить возврат:
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);
}
Комментарии:
1. Но это больше не по порядку, это становится обходом по предварительному заказу. И по-прежнему всегда возвращает false
2. @JAM Вы никогда не упоминали inorder. Это BST?
3. Это двоичное дерево, но не BST
4. Обновленный ответ будет возвращать
undefined
вместо false теперь для значений, которые находятся в дереве