二叉树路径总和：深度优先搜索解法

"18_路径总和||.pdf" 这篇资料主要讨论了二叉树中的一个算法问题——路径总和。路径总和是指在给定的二叉树中，找出所有从根节点到子节点的路径，使得路径上所有节点值之和等于给定的目标值。这个问题通常使用深度优先搜索（DFS）来解决。 首先，我们来看一下这个问题的示例。例如，给定的二叉树结构如下： ``` 5 / \ 4 8 / \ / \ 11 4 7 2 \ 5 / 1 ``` 目标和是22，我们需要找到所有从根节点5到子节点的路径，使得路径上的节点值之和为22。满足条件的路径有两条：[5, 4, 11, 2] 和 [5, 8, 4, 5]。 解决这个问题的方法是深度优先搜索。深度优先搜索是一种递归策略，用于遍历或搜索树或图。在这个问题中，我们从根节点开始，每次访问一个节点时，我们将节点值加到当前路径的总和中，并更新目标和。如果遍历到的是一个叶子节点（即没有子节点的节点），并且当前路径的总和等于目标和，那么我们就找到了一个符合条件的路径，并将其添加到结果列表中。 以下是Java实现的DFS算法： ```java class Solution { List<List<Integer>> ret = new LinkedList<List<Integer>>(); Deque<Integer> path = new LinkedList<Integer>(); public List<List<Integer>> pathSum(TreeNode root, int targetSum) { dfs(root, targetSum); return ret; } public void dfs(TreeNode root, int targetSum) { if (root == null) { return; } path.offerLast(root.val); targetSum -= root.val; if (root.left == null && root.right == null && targetSum == 0) { ret.add(new LinkedList<Integer>(path)); } dfs(root.left, targetSum); dfs(root.right, targetSum); path.pollLast(); } } public class TreeNode { int val; TreeNode left; TreeNode right; } ``` 在这个Java代码中，`Solution`类包含了两个方法：`pathSum`是主方法，它调用`dfs`进行深度优先搜索。`dfs`方法接收当前节点和目标和作为参数。每当访问一个节点，就将节点值放入`path`队列中，然后检查是否到达叶子节点且路径和等于目标和。如果是，则将路径添加到结果列表`ret`中。最后，当回溯时，从`path`队列中移除当前节点，继续搜索其他路径。 路径总和问题是一个经典的二叉树遍历问题，通过深度优先搜索策略可以有效地找到所有符合条件的路径。在实际编程中，这种问题经常出现在数据结构和算法的面试和考试中，因此理解和掌握这个算法对提升编程技能非常有帮助。