二叉树的所有路径

怎样从“根到叶所有路径字符串。”推导出 二叉树 · 所有路径，并证明每次状态变化都不会漏掉答案？

中心结论：DFS path 累加,到叶 push "1->2->3"。

给定一个二叉树，返回所有从根节点到叶子节点的路径。说明: 叶子节点是指没有子节点的节点。

在本站主例中，根到叶所有路径字符串。

算法最终需要得到或观察：["1->2->5","1->3"] 等。

从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“递归回执树”，明确答案需要观察什么。
2. 2状态只维护 path 字符串、结果。
3. 3转移每一步按照 DFS path 累加,到叶 push "1->2->3"。
4. 4收尾读取 ["1->2->5","1->3"] 等。，并复核边界与复杂度。

先用一句话定义递归函数返回什么，父节点才能正确合并。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：path 字符串、结果。

Google 的面试题，考察递归

DFS path 累加,到叶 push "1->2->3"。

执行过程中持续维护：path 字符串、结果。

正确性依赖以下不变量：叶结点才收集完整路径。

面试时可以压缩为：DFS 回溯 O(n)。

落到当前题，执行机制可以压缩为：DFS path 累加,到叶 push "1->2->3"。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入根到叶所有路径字符串。 因为：DFS path 累加,到叶 push "1->2->3"。
2. 2递归栈:根-左-右从根开始 DFS。 因为：前序第一个输出根。
3. 3访问结点 1记录当前结点。 因为：根在子树之前被访问。
4. 4访问结点 2记录当前结点。 因为：根在子树之前被访问。
5. 5访问结点 5记录当前结点。 因为：根在子树之前被访问。
6. 6访问结点 3记录当前结点。 因为：根在子树之前被访问。
7. 7前序结果: 1 → 2 → 5 → 3栈空,输出完整。 因为：O(n) 访问每个结点一次。
8. 8收尾与复杂度["1->2->5","1->3"] 等。 因为：时间 O(n) · 空间 O(1)。DFS path 累加,到叶 push "1->2->3"。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

import (
	"strconv"

)

// TreeNode define
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func binaryTreePaths(root *TreeNode) []string {
	if root == nil {
		return []string{}
	}
	res := []string{}
	if root.Left == nil && root.Right == nil {
		return []string{strconv.Itoa(root.Val)}
	}
	tmpLeft := binaryTreePaths(root.Left)
	for i := 0; i < len(tmpLeft); i++ {
		res = append(res, strconv.Itoa(root.Val)+"->"+tmpLeft[i])
	}
	tmpRight := binaryTreePaths(root.Right)
	for i := 0; i < len(tmpRight); i++ {
		res = append(res, strconv.Itoa(root.Val)+"->"+tmpRight[i])
	}
	return res
}

func main() {
    // 1. 主例
    //    输入：mode="preorder", values=[1,2,3,null,5]
    //    期望：["1->2->5","1->3"] 等。
    //
    // 2. 失败 / 未命中
    //    检查：内部结点不要收集。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC112 路径和；LC124 最大路径
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意根到叶所有路径字符串。
2. 2重复从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。
3. 3优化DFS path 累加,到叶 push "1->2->3"。
4. 4证明叶结点才收集完整路径。
5. 5复杂度时间 O(n)，空间 O(1)