难度: Easy
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]
示例 2：
输入：root = [1] 输出：["1"]
提示：
- 树中节点的数目在范围
[1, 100]内 -100 <= Node.val <= 100
Submission
运行时间: 32 ms
内存: 15 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
result = []
def dfs(root, path):
if root is None:
return
path.append(root.val)
if root.left is None and root.right is None:
result.append('->'.join([str(i) for i in path]))
dfs(root.left, path)
dfs(root.right, path)
path.pop()
dfs(root, [])
return result
Explain
该题解使用深度优先搜索(DFS)的方式遍历二叉树。从根节点开始，递归地遍历左右子树，并在遍历过程中维护一个路径数组path。当遇到叶子节点时，将当前路径加入结果数组result中。遍历完一条路径后，需要回溯，即从path中移除当前节点，继续遍历其他路径。
时间复杂度: O(n*h)，其中n为节点数，h为树的高度。最坏情况下O(n^2)，最好情况下O(n*log(n))。
空间复杂度: O(n)，其中n为节点数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
result = []
def dfs(root, path):
if root is None:
return
path.append(root.val)
# 当前节点是叶子节点，将路径加入结果数组
if root.left is None and root.right is None:
result.append('->'.join([str(i) for i in path]))
# 递归遍历左子树
dfs(root.left, path)
# 递归遍历右子树
dfs(root.right, path)
# 回溯，从路径中移除当前节点
path.pop()
dfs(root, [])
return result
Explore
在深度优先搜索（DFS）中，回溯是为了确保在遍历树的过程中每次回到父节点时，路径数组path能够准确地反映从根节点到当前节点的路径。执行pop操作是为了移除当前节点，从而在返回父节点后，可以正确地探索其他可能的路径（如兄弟节点）。这样，每次递归调用结束返回上一级调用时，path都会恢复到进入当前节点前的状态，确保路径数组的正确性。
在DFS中，每次递归调用时将当前节点的值加入到path列表中。由于递归调用是按照函数调用栈的顺序执行的，因此path列表会随着递归的深入逐步扩展，直到到达叶子节点。在递归返回之前执行pop操作，确保在返回父节点时，从path中移除当前节点，这样path恢复到父节点的状态，为进一步的遍历准备好正确的路径环境。这种方法保证了在每个递归层级，path都精确地表示从根节点到当前节点的路径。
节点值为负数不会影响DFS的逻辑或路径的存储方式，但它会影响生成的路径字符串的外观。负数会在数字前加上负号（'-'），这可能使路径字符串看起来更长或在视觉上更复杂。然而，从技术上讲，处理方式相同，即每个节点值都会被转换为字符串，并用'->'连接起来。因此，无论节点值是正数还是负数，都可以用同样的方法生成和存储路径字符串。
是的，算法确实考虑了二叉树只有一个节点的情况。当二叉树仅有一个节点时，该节点既是根节点也是叶子节点。在DFS函数中，如果一个节点既没有左子树也没有右子树，就会被视为叶子节点。对于只有一个节点的树，DFS会将这个根节点添加到path中，随即检测到它是叶子节点，因此会直接将其路径（即它自己）加入到结果数组。这样，即使树中只有一个节点，也能正确生成其路径。