#javascript #algorithm #recursion #binary-tree
#язык JavaScript #алгоритм #рекурсия #двоичное дерево
Вопрос:
Может ли кто-нибудь объяснить мне, почему данный код используется для обхода двоичного дерева:
var sumOfLeftLeaves = function(root) { let sum = 0; traverse(root, sum); return sum; }; function traverse(root, sum) { const left = root.left; const right = root.right; if (left) { sum = left.val; traverse(left, sum); } if (right) { traverse(right, sum); } } сумма, которая была правильно рассчитана во время обхода дерева, сбрасывается до 0 после выхода из последнего рекурсивного этапа?
Ответ №1:
var sumOfLeftLeaves = function(root) { let sum = 0; return traverse(root, sum); }; function traverse(root, sum) { const left = root.left; const right = root.right; sum = root.val if (left) { sum = traverse(left, sum); } if (right) { sum = traverse(right, sum); } return sum } sum это непреложная ценность. Это означает, что каждый раз, когда вы передаете его в качестве аргумента для вызова функции, создается новая копия. Таким образом, добавления, которые вы делаете дальше по рекурсивному стеку, не отражаются на sum переменной в кадрах стека выше.
Для дальнейшего уточнения, sum является целым числом, Number в терминах JS. Это тип значения, означающий, что при каждом присвоении оно передается по значению, копируется заново. Другими словами, среда выполнения JS создает новое место в стеке и сохраняет значение, назначенное в новом месте. Любая мутация/модификация, которую вы вносите в тип значения, не отражается на исходной переменной.
Такой подход решает проблему.
Другим подходом было бы удалить sum в качестве параметра и возвращать только сумму значений узлов следующим образом:
var sumOfLeftLeaves = function(root) { return traverse(root); }; function traverse(root) { if (root == null) return 0 return root.val traverse(root.left) traverse(root.right); } Для полноты картины третьим подходом было бы создание sum изменяемой переменной, такой как тип объекта js или массив. В то время как сама структура объекта или массива передается по значению, их содержимое может быть изменено, и эти изменения будут отражены в исходной переменной. Допустим, вы передаете sum как массив из одного элемента, const sum = [0] . Всякий раз, когда вы что-то добавляете в него sum[0] = node.val , значение элемента с нулевым индексом sum изменяется, а также отображается для функций, расположенных выше стека вызовов.
Комментарии:
1. Так почему же сумма неизменна? Не могли бы вы поподробнее рассказать об этом?
2. Конечно, я добавил его к ответу, так как он не поместился бы в комментариях.
3. Большое спасибо!
4. Я добавил еще несколько комментариев в конце, которые могут помочь, если вы хотите продолжить тестирование и изучение.
5. Я действительно запутался, так как обычно использую не javascript, а машинопись. Теперь я на самом деле не уверен, использовал ли я когда-либо числа в рекурсивных функциях и изменил исходное число или это был объект. Я не уверен, есть ли разница между этими двумя языками в этом отношении, или я просто тупой. Вероятно, последнее
Ответ №2:
Вы не возвращаетесь sum оттуда traverse и тоже не переназначаете его sumOfLeftLeaves . Вы, наверное, хотите чего-то большего, как это:
var sumOfLeftLeaves = function(root) { return traverse(root, 0); }; function traverse(root, sum) { const left = root.left; const right = root.right; if (left) { sum = left.val; return traverse(left, sum); } if (right) { return traverse(right, sum); } return sum; } Ответ №3:
Вы можете использовать одну функцию, которая возвращает либо значение плюс левая и правая стороны, либо ноль.
const sumOfTree = node =gt; node ? value sumOfTree(node.left) sumOfTree(node.right) : 0; Другим решением может быть использование функции обхода, которая принимает значение узла и функции с замыканием над объектом.
const traverse = (node, fn) =gt; { if (!node) return; fn(node); traverse(node.left, fn); traverse(node.right, fn); }, sumOfTree = result =gt; node =gt; result.sum = node.value; // call const result = { sum: 0 }, getSum = sumOfTree(result); traverse(tree, getSum); console.log(result.sum); Комментарии:
1. Я всегда учусь на ваших реализациях js.