JavaScript实现二叉树所有路径的DFS遍历 | 代码示例与解释

在二叉树中，所有路径指的是从根节点到叶子节点的路径。我们可以使用深度优先搜索（DFS）来遍历二叉树，并记录每条路径。以下是使用JavaScript实现的代码示例：

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

function binaryTreePaths(root) {
    const paths = [];

    function dfs(node, path) {
        if (!node) return;

        // 将当前节点的值加入路径
        path += node.val;

        // 如果是叶子节点，将路径加入结果集
        if (!node.left && !node.right) {
            paths.push(path);
            return;
        }

        // 递归遍历左子树和右子树
        path += '->';
        dfs(node.left, path);
        dfs(node.right, path);
    }

    dfs(root, '');
    return paths;
}

// 示例用法
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.right = new TreeNode(5);

console.log(binaryTreePaths(root)); // 输出: ["1->2->5", "1->3"]

代码解释：

1. TreeNode类：定义了二叉树的节点结构，每个节点包含一个值 val，以及指向左子树和右子树的指针 left 和 right。

2. binaryTreePaths函数：这是主函数，用于找到二叉树的所有路径。

   • paths 数组用于存储所有路径。
   • dfs 函数是一个递归函数，用于深度优先遍历二叉树。
   • 在 dfs 函数中，我们首先检查当前节点是否为空。如果为空，则返回。
   • 然后将当前节点的值加入路径 path。
   • 如果当前节点是叶子节点（即没有左子树和右子树），则将当前路径加入 paths 数组。
   • 如果不是叶子节点，则在路径后添加 ->，然后递归遍历左子树和右子树。

3. 示例用法：创建了一个简单的二叉树，并调用 binaryTreePaths 函数来获取所有路径。

输出：

对于给定的二叉树：

    1
   / \
  2   3
   \
    5

输出结果为：

["1->2->5", "1->3"]

这个算法的时间复杂度是 O(N)，其中 N 是二叉树中的节点数，因为我们需要访问每个节点一次。空间复杂度也是 O(N)，主要是递归调用栈的空间消耗。