题目描述

257. 二叉树的所有路径

解题思路

1. 题意理解

   给定一棵二叉树，要求返回所有从根节点到叶子节点的路径，路径以字符串形式表示，格式如 “1->2->5”。

2. 算法选择：DFS + 回溯

   由于需要找出所有从根到叶子的路径，自然想到使用深度优先遍历（DFS）。

   同时，因为路径是一个从根开始的逐步构建过程，我们需要在递归过程中记录当前路径，并在递归返回时撤销（回溯）上一步的选择。

3. 递归终止条件

   如果遇到了 null ，向上返回

   如果遇到了 叶子节点 ，说明得到了一条新的路径，加入结果集，然后返回。

4. 路径的记录与处理

   我们使用一个数组 path 来记录当前从根节点到当前节点的路径。

   当遇到叶子节点（即 left == null && right == null）时，把 path 用 “->” 连接成字符串加入最终结果数组。

   注意：每次递归后需要 回溯（pop弹出） 上一个节点，确保路径的正确性。

5. 边界情况处理

   如果根节点为 null，直接返回空数组。

   如果树中只有一个节点，也能正常处理为一个路径。

更直观的理解：
想象你正站在一棵树的某个节点上，此时路径数组（path）中保存的是从根节点到当前节点所经过的路径。
接下来，你需要继续从当前节点出发，分别向的左子树和右子树递归前进。
当你遇到空节点或叶子节点（即递归的终止条件）时，说明当前这条路径已经走到尽头，此时会开始从下往上返回，并在返回的过程中撤销刚刚加入的路径节点（这一步是“回溯”），以便尝试其他分支的路径。

完整代码

递归写法，也可以用迭代

var binaryTreePaths = function(root) {let res = [];let path = [];function dfs(node) {if (node === null) returnpath.push(node.val);// 如果是叶子节点，就把路径加入结果if (!node.left && !node.right) {res.push(path.join('->'));return}// 继续递归左右子树dfs(node.left);dfs(node.right);// 回溯path.pop();}dfs(root);return res;
};

时间复杂度分析

• 遍历了所有节点：O(N)，其中 N 是节点数。

• 每条路径最长为树高 H，每条路径转为字符串的时间是 O(H)，总共最多 N 个叶子节点。
  所以最坏情况总时间为：O(N * H)。