Трудно понять рекурсивную часть кода - PullRequest
Новая
       49

Трудно понять рекурсивную часть кода

0 голосов
/ 06 мая 2020

Я нашел решение этой проблемы алгоритма:

Учитывая двоичное дерево, вам нужно вычислить длину диаметра дерева. Диаметр двоичного дерева - это длина самого длинного пути между любыми двумя узлами дерева. Этот путь может проходить или не проходить через root.

Пример: дано двоичное дерево 

          1
         / \
        2   3
       / \     
      4   5

Возвращает 3, то есть длину пути [4,2,1 , 3] или [5,2,1,3].

Примечание. Длина пути между двумя узлами представлена ​​количеством ребер между ними.

Код: 

class TreeNode {
    constructor(val, left, right) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
}

const diameterOfBinaryTree = (root) => {
    let count = 0

    const dfs = (c) => {
        if (!c) return 0

        let left = dfs(c.left) // is this just going to the last node?
        let right = dfs(c.right) //what do left and right equal?
        count = Math.max(count, left + right) //since I don't know what left or right are 
                                              //it's hard to understand what I am comparing

        return 1 + Math.max(left, right) //why are we adding 1
    }
    dfs(root)
    return count
}


const tree = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3))

Итак, у меня следующие вопросы: чему назначены левая и правая? Почему мы добавляем 1 к возвращаемому значению?

Я пытался использовать инструменты разработчика chrome, добавляя точку останова в каждую строку, которую я прокомментировал в коде, чтобы пройти через нее, но я все еще запутался относительно того, что происходит. Есть ли особый способ консольного журнала каждой итерации, чтобы я мог видеть, как меняются значения? Мне не удалось получить значения консольного журнала, когда функция рекурсивна, любая помощь была бы отличной.

...