Итак, вы начали изучать алгоритмы для собеседования по программированию. Удачи вам и ваших дальнейших начинаниях! Но сначала вы должны взяться за двоичное дерево.
Двоичное дерево - это структура, которая имеет один корневой узел, который затем разветвляется на два левых и правых узла. Они называются дочерними узлами. Эти два левого и правого узла могут ответвляться еще на два левого и правого узла и так далее.
Чтобы вычислить суммы каждой ветви, мы должны начать с корневого узла. В корневом узле сумма равна 0, потому что мы еще не начали добавлять ветки. Давайте разберем это на функцию Javascript. На собеседовании по кодированию вам, скорее всего, придется решить следующую проблему:
Ваша функция сможет принимать только один аргумент: корневой узел. Поэтому нам нужно создать вспомогательную функцию, которая сможет отслеживать массив различных сумм, текущую сумму, с которой мы работаем на каждом уровне двоичного дерева, и то, на каком узле мы находимся. Сначала мы создадим наш пустой массив сумм, а затем передадим его, runningSum (который будет инициализирован на 0) и текущий узел, на котором мы находимся, в нашу вспомогательную функцию. В конце мы хотим вернуть массив сумм ветвей, поэтому обязательно запишем это в наш код.
Теперь мы начинаем писать нашу вспомогательную функцию calculateBranchSums. Прежде чем мы продолжим нашу функцию, мы хотим проверить, существует ли вообще узел, который мы передаем. Итак, давайте возьмем это за основу для нашей функции.
Если узел не соответствует действительности, просто вернитесь. Затем мы хотим вычислить runningSum. Это новая сумма, которая отражает значение текущего узла узла и всех узлов перед ним. После этого нам нужно будет определить, находимся ли мы в самой нижней ветви дерева. Другими словами, нам нужно проверить, что текущий узел не имеет дочерних узлов. Итак, мы скажем: «Если на нашем текущем узле нет левого узла и нет правого узла», то….
Если мы действительно находимся в нижней ветви нашего дерева, то мы хотим добавить эту newRunningSum в наш массив sums.
Однако, если мы не находимся в нижней части нашего дерева, мы хотим рекурсивно вызывать эту функцию, чтобы заботиться о дочерних узлах. Итак, вне нашего оператора If, давайте передадим значение правого дочернего узла узла, новую текущую сумму и массив сумм в нашу функцию. Мы сделаем то же самое для значения левого потомка узла.
К концу наша полная функция будет выглядеть так:
Вот как вы вычисляете суммы ветвей двоичного дерева в Javascript!
