257. 二叉树的所有路径
题目描述
输入一棵二叉树的根节点 root，树用层序数组表示，空位记为 null。
没有任何孩子的节点叫叶子节点。找出从根走到每一个叶子的路径。
每条路径写成一个字符串：把沿途节点的值依次用 "->" 连起来。返回所有路径字符串，顺序不限。
示例 1
输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]
解释：叶子有 5 和 3，两条路径分别是 1->2->5 和 1->3。
示例 2
输入：root = [1] 输出：["1"]
解释：根自己就是叶子。
数据范围
- 节点个数在
[1, 100]之间。 -100 <= Node.val <= 100
解题思路：深度优先搜索
深度优先遍历，递归时带上“从根走到当前节点”的路径字符串。进入节点就把它的值拼到末尾；如果是叶子，整条路径就是一个答案；否则在末尾加上 "->"，分别递归进入非空的左、右孩子。字符串是不可变的，每层持有自己的副本，回到上层时无需手动撤销。
为什么正确
调用 dfs(node, path) 时，path 等于从根到 node 父节点的路径并以 "->" 结尾（根节点时为空串）。
复杂度分析
时间 O(n·h)（拼接字符串），空间 O(h) 递归栈，不计输出。
易错点
只在叶子处记录路径。如果在空节点处记录，只有一个孩子的节点会把空的那一侧当作路径终点，产生重复或错误的路径。另外节点值可能为负，要用 str() 转换，而不是拼接字符。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
res = []
def dfs(node, path):
path = path + str(node.val)
if not node.left and not node.right:
res.append(path)
return
if node.left:
dfs(node.left, path + '->')
if node.right:
dfs(node.right, path + '->')
dfs(root, '')
return resclass Solution {
List<String> res = new ArrayList<>();
void dfs(TreeNode node, String path) {
path = path + node.val;
if (node.left == null && node.right == null) {
res.add(path);
return;
}
if (node.left != null) {
dfs(node.left, path + "->");
}
if (node.right != null) {
dfs(node.right, path + "->");
}
}
public List<String> binaryTreePaths(TreeNode root) {
dfs(root, "");
return res;
}
}class Solution {
public:
vector<string> res;
void dfs(TreeNode* node, string path) {
path += to_string(node->val);
if (!node->left && !node->right) {
res.push_back(path);
return;
}
if (node->left) {
dfs(node->left, path + "->");
}
if (node->right) {
dfs(node->right, path + "->");
}
}
vector<string> binaryTreePaths(TreeNode* root) {
dfs(root, "");
return res;
}
};func binaryTreePaths(root *TreeNode) []string {
res := []string{}
var dfs func(node *TreeNode, path string)
dfs = func(node *TreeNode, path string) {
path += strconv.Itoa(node.Val)
if node.Left == nil && node.Right == nil {
res = append(res, path)
return
}
if node.Left != nil {
dfs(node.Left, path+"->")
}
if node.Right != nil {
dfs(node.Right, path+"->")
}
}
dfs(root, "")
return res
}var binaryTreePaths = function(root) {
const res = [];
const dfs = (node, path) => {
path = path + node.val;
if (!node.left && !node.right) {
res.push(path);
return;
}
if (node.left) {
dfs(node.left, path + '->');
}
if (node.right) {
dfs(node.right, path + '->');
}
};
dfs(root, '');
return res;
};function binaryTreePaths(root: TreeNode | null): string[] {
const res: string[] = [];
const dfs = (node: TreeNode, path: string): void => {
path = path + node.val;
if (!node.left && !node.right) {
res.push(path);
return;
}
if (node.left) {
dfs(node.left, path + '->');
}
if (node.right) {
dfs(node.right, path + '->');
}
};
dfs(root!, '');
return res;
}其他解法
DFS 沿一条路走到叶子，由递归参数携带路径；BFS 按层扩展，把路径和节点一起放进队列。两者复杂度相同，只是遍历顺序不同。
解法 2：广度优先搜索 时间 O(n²)，空间 O(n²)
队列中同时保存节点和从根到该节点的路径字符串。每次取出一对：如果是叶子，就把路径加入答案；否则把子节点连同“路径 + '->' + 子节点值”一起入队。
不用递归，深链树不会栈溢出。队列里要存每个节点的路径副本，输出顺序按叶子深度排列，和 DFS 不同。
from collections import deque
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
res = []
q = deque([(root, str(root.val))])
while q:
node, path = q.popleft()
if not node.left and not node.right:
res.append(path)
continue
for child in (node.left, node.right):
if child:
q.append((child, path + '->' + str(child.val)))
return resclass Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();
Deque<TreeNode> nodes = new ArrayDeque<>();
Deque<String> paths = new ArrayDeque<>();
nodes.offer(root);
paths.offer(String.valueOf(root.val));
while (!nodes.isEmpty()) {
TreeNode node = nodes.poll();
String path = paths.poll();
if (node.left == null && node.right == null) {
res.add(path);
continue;
}
for (TreeNode child : new TreeNode[]{node.left, node.right}) {
if (child != null) {
nodes.offer(child);
paths.offer(path + "->" + child.val);
}
}
}
return res;
}
}class Solution {
public:
vector<string> binaryTreePaths(TreeNode* root) {
vector<string> res;
queue<pair<TreeNode*, string>> q;
q.emplace(root, to_string(root->val));
while (!q.empty()) {
auto [node, path] = q.front();
q.pop();
if (!node->left && !node->right) {
res.push_back(path);
continue;
}
for (TreeNode* child : {node->left, node->right})
if (child) q.emplace(child, path + "->" + to_string(child->val));
}
return res;
}
};func binaryTreePaths(root *TreeNode) []string {
type item struct {
node *TreeNode
path string
}
res := []string{}
q := []item{{root, strconv.Itoa(root.Val)}}
for len(q) > 0 {
cur := q[0]
q = q[1:]
if cur.node.Left == nil && cur.node.Right == nil {
res = append(res, cur.path)
continue
}
for _, child := range []*TreeNode{cur.node.Left, cur.node.Right} {
if child != nil {
q = append(q, item{child, cur.path + "->" + strconv.Itoa(child.Val)})
}
}
}
return res
}var binaryTreePaths = function(root) {
const res = [];
const q = [[root, String(root.val)]];
for (let h = 0; h < q.length; h++) {
const [node, path] = q[h];
if (!node.left && !node.right) {
res.push(path);
continue;
}
for (const child of [node.left, node.right])
if (child) q.push([child, path + '->' + child.val]);
}
return res;
};function binaryTreePaths(root: TreeNode | null): string[] {
const res: string[] = [];
const q: [TreeNode, string][] = [[root!, String(root!.val)]];
for (let h = 0; h < q.length; h++) {
const [node, path] = q[h];
if (!node.left && !node.right) {
res.push(path);
continue;
}
for (const child of [node.left, node.right])
if (child) q.push([child, path + '->' + child.val]);
}
return res;
}