LeetCode 257. 二叉树所有路径求解：回溯算法的深度解析与实践-EW帮帮网

一、题目解析：二叉树路径的遍历需求

题目描述

给定一棵二叉树，返回所有从根节点到叶子节点的路径。例如，对于如下二叉树：

应返回 ["1->2->4", "1->3"]。

问题本质

路径定义：从根节点到叶子节点的一条完整路径（叶子节点指没有子节点的节点）。
核心需求：遍历所有可能的路径，并将路径上的节点值按顺序拼接成字符串。

解题关键点

路径的动态构建：在遍历过程中动态记录当前路径。
回溯机制：当到达叶子节点后，需要回退到上一层继续探索其他路径。
递归终止条件：当到达叶子节点时，将当前路径加入结果集。

二、回溯算法核心：从递归到状态恢复的完整流程

回溯算法基本概念

回溯算法本质是一种试错思想，通过递归尝试所有可能的路径，当发现当前路径不符合要求时（如已到达叶子节点），回退到上一层状态，继续探索其他可能。

本题回溯算法的核心要素

状态定义：
- temp 列表：存储当前路径上的节点值。
- res 列表：存储所有符合条件的路径字符串。
递归终止条件：
当当前节点为叶子节点（左右子节点均为空）时，将临时路径转换为字符串并加入结果集。
状态转移与回溯：
- 递归进入子节点前，将当前节点值加入临时路径。
- 从子节点返回后，移除临时路径的最后一个节点值（回溯），恢复到进入子节点前的状态。

三、代码解析：回溯算法的具体实现

完整代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        List<Integer> temp = new ArrayList<>();
        traversal(root, res, temp);
        return res;
    }

    public static void traversal(TreeNode root, List<String> res, List<Integer> temp) {
        temp.add(root.val); // 1. 记录当前节点到临时路径
        
        // 2. 到达叶子节点，处理路径
        if (root.left == null && root.right == null) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < temp.size() - 1; i++) {
                sb.append(temp.get(i)).append("->");
            }
            sb.append(temp.get(temp.size() - 1));
            res.add(sb.toString());
            return;
        }
        
        // 3. 递归处理左子树
        if (root.left != null) {
            traversal(root.left, res, temp);
            temp.remove(temp.size() - 1); // 回溯：移除左子树添加的节点
        }
        
        // 4. 递归处理右子树
        if (root.right != null) {
            traversal(root.right, res, temp);
            temp.remove(temp.size() - 1); // 回溯：移除右子树添加的节点
        }
    }
}

代码核心步骤拆解

1. 路径记录与状态维护

temp.add(root.val);

每次递归进入节点时，将当前节点值添加到临时路径，形成动态增长的路径记录。

2. 叶子节点处理

if (root.left == null && root.right == null) {
    // 转换路径为字符串
}

当当前节点为叶子节点时，临时路径已形成完整路径，将其转换为字符串（如1->2->4）并加入结果集。

3. 递归与回溯的关键

traversal(root.left, res, temp);
temp.remove(temp.size() - 1);

递归进入左子树后，temp列表包含从根到左子树的路径。
temp.remove(temp.size() - 1)：从左子树回溯时，移除最后一个节点值，恢复到进入左子树前的状态，以便探索右子树。

四、回溯流程模拟：以示例二叉树为例

示例二叉树结构

详细执行过程

初始状态：
- root=1，temp=[1]，进入左子树（节点2）。
处理节点2：
- temp=[1,2]，进入左子树（节点4）。
处理节点4：
- temp=[1,2,4]，节点4是叶子节点，转换路径为"1->2->4"，加入res。
- 回溯：移除4，temp=[1,2]，返回节点2。
处理节点2的右子树：
- 节点2的右子树为空，继续回溯：移除2，temp=[1]，返回节点1。
处理节点1的右子树（节点3）：
- temp=[1,3]，节点3是叶子节点，转换路径为"1->3"，加入res。
- 回溯：移除3，temp=[1]，返回根节点，遍历结束。

回溯过程图解

根节点1 → 添加1到temp → 进入左子树2
节点2 → 添加2到temp → 进入左子树4
节点4 → 添加4到temp → 是叶子节点，记录路径"1->2->4"
       → 回溯：移除4，temp=[1,2]
节点2 → 右子树为空，回溯：移除2，temp=[1]
根节点1 → 进入右子树3
节点3 → 添加3到temp → 是叶子节点，记录路径"1->3"
       → 回溯：移除3，temp=[1]
遍历结束，res=["1->2->4", "1->3"]

五、回溯算法的核心思想：状态机与递归栈

回溯的本质：状态机的递归实现

状态机要素：
- 当前路径（temp列表）是状态的核心载体。
- 递归调用是状态转移，remove操作是状态回退。
递归栈的作用：
递归栈隐式保存了每个节点的调用上下文，当从子节点返回时，自动恢复到父节点的状态，配合temp.remove实现精确的状态恢复。

回溯与DFS的关系

本题使用的是深度优先搜索（DFS） 的思想，通过回溯算法实现：
- DFS保证遍历所有可能的路径。
- 回溯确保在探索完一条路径后，能回退到上一层继续探索其他路径。

六、复杂度分析与优化思考

时间复杂度

O(n×2^h)：其中n为节点数，h为树的高度。
- 每个节点至少访问一次（O(n)）。
- 路径长度平均为O(h)，最坏情况下（如链表树）路径长度为O(n)，拼接字符串的总时间为O(n×2^h)。

空间复杂度

O(h)：递归栈的深度为树的高度h，临时路径temp的长度也为h。

优化方向

字符串拼接优化：
用StringBuilder代替字符串拼接，避免频繁创建新字符串。
路径重建优化：
可通过记录路径字符串而非节点列表，减少回溯时的操作（但会增加字符串操作开销）。

七、回溯算法通用模板与拓展应用

回溯算法通用框架

void backtrack(参数) {
    if (终止条件) {
        处理结果;
        return;
    }
    
    for (选择 in 所有可能的选择) {
        做选择;
        backtrack(参数);
        撤销选择; // 回溯
    }
}

本题与通用框架的对应

终止条件：到达叶子节点。
做选择：将节点值加入临时路径。
撤销选择：从临时路径移除节点值。

拓展应用场景

组合问题：如LeetCode 77. 组合。
排列问题：如LeetCode 46. 全排列。
子集问题：如LeetCode 78. 子集。
数独求解：经典的回溯应用场景。

八、总结：回溯算法的核心要点

状态维护：
清晰定义状态（如本题的temp路径），并在递归过程中正确维护状态。
终止条件：
明确何时停止递归并处理结果（如到达叶子节点）。
回溯机制：
递归返回前必须撤销当前选择，恢复到之前的状态（如temp.remove）。
递归顺序：
确保递归顺序符合问题要求（如本题的先左后右遍历）。

理解回溯算法的关键在于将其视为“有记忆的DFS”，通过状态的动态维护与恢复，实现对所有可能解的系统探索。在树结构中，回溯算法天然匹配树的递归结构，成为求解路径问题的高效手段。

LeetCode 257. 二叉树所有路径求解：回溯算法的深度解析与实践