SOURCE

// 思路
// 使用前序遍历 每递归一个节点记录路径 直到找到叶子节点 记录一条路径
// 通过递归的出栈返回前一个节点 寻找其他可能的路径
// 本题用到了一点回溯的思想 回溯是递归过程中寻找全部解的 策略
// 如果路径用数组保存 则需要在递归出栈时进行回溯
// 也可以利用JS基本类型没有引用地址的特性 从而隐性的回溯

class Node {
    constructor(value, left, right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

let n1 = new Node(1, null, null);
let n2 = new Node(2, null, null);
let n4 = new Node(4, n1, n2);
let n6 = new Node(6, null, null);
let root = new Node(5, n4, n6);

function fn(root) {
    let 路径集合 = []

    // path为数组时
    function 寻找路径(node, path = []) {
        // 因为父级递归已经过滤了空节点 因此不需要判断 node == null 的情况 只需要判断子节点是否为空
        // 将当前节点值装入路径
        path.push(node.value)
        // 递归出口 当前节点没有孩子节点 说明已找到叶子节点
        if (node.left == null && node.right == null) {
            // 记录路径
            let str = ''
            // 遍历除末尾节点的路径
            for (let i = 0; i < path.length - 1; i++) {
                // path中存的每一个节点值用 ->号 连接
                str += path[i] + '->'
            }
            // 再添加末尾节点
            str += path[path.length - 1]
            // 结束递归 添加到结果数组 并出栈到上一层递归
            路径集合.push(str)
            return
        }
        // 当前节点不是叶子节点 继续递归子节点
        if (node.left) {
            // 有子节点 则继续递归
            寻找路径(node.left, path)
            // 从递归返回 对路径进行 回溯 将刚递归添加的节点值剔出 寻找其他路径
            path.pop()
        }
        if (node.right) {
            寻找路径(node.right, path)
            path.pop()
        }
    }

    // 对比path为字符串时
    function 寻找路径2(node, path = '') {
        // 此处改为字符串拼接
        path += node.value
        if (node.left == null && node.right == null) {
            // 是叶子节点 直接添加path到结果数组
            路径集合.push(path)
            return
        }
        // 不是叶子节点 则在path后拼接 ->符号
        path += '->'
        // 注意 因为path是基本类型数据 因此不会被下一层递归影响 相当于隐性 回溯
        node.left && 寻找路径2(node.left, path)
        node.right && 寻找路径2(node.right, path)
    }

    // 寻找路径(root)
    寻找路径2(root)
    return 路径集合
}

// 验证
console.log('所有路径', fn(root))