Возникли проблемы с пониманием рекурсивной части двоичного дерева DFS

Question

Я написал эту функцию методом проб и ошибок, и я не могу понять, как рекурсивная часть добавляет первый элемент или, в данном случае, 1-> в обоих путях. Вот код:

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = this.right = null;
    }
}

const binaryTreePaths = root => {
    if (!root) return null
    let results = []
    const dfs = (node, path) => {
        if (!node.left && !node.right) return results.push(path + node.val)
        if (node.left) dfs(node.left, path + node.val + '->')
        if (node.right) dfs(node.right, path + node.val + '->')
    }
    dfs(root, '')
    return results
}

const tree1 = new TreeNode(1)
tree1.left = new TreeNode(2)
tree1.right = new TreeNode(3)
tree1.left.right = new TreeNode(5)

console.log(binaryTreePaths(tree1))

Рекурсивные вызовы левого и правого узлов добавляют левого и правого потомков к пути, который я понимаю, но что в функции добавляет первый узел?

Answer 1

Это может помочь немного реорганизовать функцию:

const dfs = (node, parentPath) => {
    const path = parentPath + node.val;
//                          ^^^^^^^^^^ magic happens here
    if (!node.left && !node.right) return results.push(path)
    if (node.left) dfs(node.left, path + '->')
    if (node.right) dfs(node.right, path + '->')
}

Попробуйте пройти через это с помощью отладчика и запишите значения parentPath и path.