T257_binaryTreePaths

257. 二叉树的所有路径

题目

介绍

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

示例：

输入:

1 /
2 3
5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

解法

方法一 回溯法

思路

1. 定义 res 用于 存储结果；
2. 定义一个 path 用于存储 路径；
3. 将当前节点值 加入 path ： path.append(str(root.val));
4. 判断 当前节点是否 叶子 节点：
   1. 是，将 path 加入 res: sres.append("->".join(path))
   2. 回退：path.pop()
5. 判断 左子树 是否存在：
   1. 是，左子树遍历；
6. 判断右子树 是否存在：
   1. 是，右子树遍历；

复杂度计算

时间复杂度：O(n)

空间复杂度：O(logn)