树.回溯思想.路径总和 II

路径总和 II 是一个经典的树形回溯问题，其核心在于通过深度优先搜索（DFS）遍历所有可能的路径，并在遍历过程中记录满足条件的路径。以下是详细的解答：

核心思路

枚举所有路径：从根节点出发，递归遍历每个子节点，记录路径上的节点值。
检查路径和：在到达叶子节点时，判断当前路径的和是否等于目标值。
回溯处理：在递归返回时，需要移除当前节点，确保路径记录的正确性。

关键步骤

递归终止条件：
当前节点为空时，直接返回。
当前节点是叶子节点（无左右子节点）且路径和等于目标值时，将路径加入结果集。
递归过程：
将当前节点值加入路径。
更新剩余目标和（targetSum - node.val）。
递归处理左子树和右子树。
回溯：移除路径中的当前节点值，避免影响其他路径的记录。

代码实现（减法模式）class Solution { public List<List<Integer>> pathSum(TreeNode root, int targetSum) { List<List<Integer>> res = new ArrayList<>(); List<Integer> path = new ArrayList<>(); dfs(root, targetSum, path, res); return res; } private void dfs(TreeNode node, int target, List<Integer> path, List<List<Integer>> res) { if (node == null) return; path.add(node.val); int curr = target - node.val; // 叶子节点且路径和满足条件 if (node.left == null && node.right == null && curr == 0) { res.add(new ArrayList<>(path)); } // 递归左右子树 dfs(node.left, curr, path, res); dfs(node.right, curr, path, res); // 回溯：移除当前节点 path.remove(path.size() - 1); }}代码解析

输入与初始化：
root：二叉树的根节点。
targetSum：目标和。
res：存储所有满足条件的路径。
path：记录当前路径的节点值。
递归函数 dfs：
参数：当前节点 node，剩余目标和 target，当前路径 path，结果集 res。
终止条件：节点为空时返回。
路径更新：将当前节点值加入 path，并计算剩余目标和 curr。
叶子节点检查：如果是叶子节点且 curr == 0，将当前路径加入 res。
递归与回溯：分别处理左右子树，并在返回时移除 path 的最后一个节点。
回溯的必要性：
路径 path 是共享变量，递归过程中会被修改。
回溯确保每次递归返回后，path 恢复到进入该节点前的状态，避免污染其他路径。

示例分析

以输入 root = [5,4,8,11,null,13,4,7,2,null,null,5,1]，targetSum = 22 为例：

路径 [5,4,11,2]：
5 → 4 → 11 → 2，和为 22，满足条件。
路径 [5,8,4,5]：
5 → 8 → 4 → 5，和为 22，满足条件。
其他路径：
如 [5,8,13] 和为 26 ≠ 22，不满足条件。

最终输出：[[5,4,11,2], [5,8,4,5]]。

复杂度分析

时间复杂度：O(N2)，其中 N 是节点数。最坏情况下（树为链表），每条路径需要 O(N) 时间复制到结果中。
空间复杂度：O(N)，递归栈深度和路径存储的空间。

总结

通过深度优先搜索和回溯，可以高效地枚举所有路径并检查路径和。关键在于：

递归终止条件的准确判断。
回溯操作的正确执行，确保路径记录的独立性。
减法模式优化，避免重复计算路径和。

您可能感兴趣问答

Collapsible

热门标签

热点问答