257. 二叉树的所有路径

# Definition for a binary tree node.
class Solution:def traversal(self, cur, path, result):path.append(cur.val)  # 中if not cur.left and not cur.right:  # 到达叶子节点sPath = '->'.join(map(str, path))result.append(sPath)returnif cur.left:  # 左self.traversal(cur.left, path, result)path.pop()  # 回溯if cur.right:  # 右self.traversal(cur.right, path, result)path.pop()  # 回溯def binaryTreePaths(self, root):result = []path = []if not root:return resultself.traversal(root, path, result)return result

代码来自代码思想录，具体细节见此网页
这段代码定义了一个用于遍历二叉树并找到从根节点到所有叶子节点路径的类 Solution。下面是代码的逐步解释：

1. 节点定义：这段代码假设已存在一个二叉树节点的类，通常结构为 TreeNode，包含 val（节点值）、left（左子节点）和 right（右子节点）属性。

2. traversal 方法：这个递归方法用于遍历树：

   • cur 参数是当前节点，path 是从根到当前节点的值的列表，result 存储所有路径的最终结果。
   • 把当前节点值 cur.val 添加到 path 列表中。
   • 判断当前节点是否是叶子节点（左右子节点都为 None）。如果是，则通过 '->' 将 path 列表中的值连接成一个字符串 sPath，并将其添加到 result 列表中。
   • 如果当前节点有左子节点，则递归调用 traversal 方法处理左子树，并在返回后使用 path.pop() 回溯，移除当前节点的值以便继续探访其他路径。
   • 同样，如果当前节点有右子节点，执行相同的处理。

3. binaryTreePaths 方法：这是主要的接口方法：

   • 创建一个空列表 result 用于保存结果路径，一个空列表 path 用于跟踪路径。
   • 如果根节点 root 为空，返回空的 result。
   • 调用 traversal 方法开始遍历，从根节点开始，最终返回所有路径的列表 result。

总结：这个类通过深度优先搜索（DFS）算法遍历二叉树，找到所有从根到叶子节点的路径，并以字符串形式返回这些路径。