java-leetcode题解之第112题路径总和.zip

《Java LeetCode题解：第112题“路径总和”》 在编程的世界里，LeetCode是一个广受欢迎的在线平台，它提供了各种算法题目，帮助开发者提升编程技巧和解决问题的能力。Java作为一门广泛使用的编程语言，是解决LeetCode问题的常用工具。今天我们将深入探讨LeetCode中的第112题——“路径总和”。 题目描述： 给定一个二叉树和一个整数`targetSum`，判断该树中是否存在从根节点到叶子节点的路径，这条路径上的所有节点值加起来等于给定的目标和`targetSum`。叶子节点是指没有子节点的节点。 这个问题是二叉树遍历的一个经典应用，主要涉及到了深度优先搜索（DFS）和广度优先搜索（BFS）两种策略。我们首先来看看如何使用DFS来解决这个问题。 DFS解法： 深度优先搜索是一种递归的遍历方式，可以沿着树的深度方向尽可能深地搜索。对于本题，我们可以从根节点开始，递归地检查每个子节点。在每次递归调用中，我们将当前节点的值与剩余目标和进行比较。如果当前节点为叶子节点且值等于剩余目标和，那么返回`true`表示找到了满足条件的路径；否则，如果当前节点不是叶子节点，我们将分别检查左子树和右子树。 以下是使用DFS的Java代码实现： ```java public boolean hasPathSum(TreeNode root, int targetSum) { if (root == null) return false; if (root.left == null && root.right == null && root.val == targetSum) return true; return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val); } ``` BFS解法： 广度优先搜索则使用队列来存储待访问的节点，从根节点开始，逐层遍历。在每层遍历中，我们同样检查当前节点是否满足条件，如果是叶子节点并且值等于剩余目标和，就返回`true`。如果不是叶子节点，我们将它的子节点加入队列继续搜索。 BFS的Java实现稍微复杂一些，需要用到`Queue<TreeNode>`数据结构： ```java public boolean hasPathSum(TreeNode root, int targetSum) { Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); if (node.left == null && node.right == null && node.val == targetSum) return true; if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } return false; } ``` 这两种方法各有优缺点。DFS通常需要较少的额外空间，但可能会导致更深的递归栈，而BFS则需要更多的空间来存储队列，但递归深度较低，可能更适用于树的层次遍历问题。在LeetCode平台上，由于内存限制，有时DFS会是更好的选择。 通过解决这类问题，我们可以锻炼对二叉树操作的理解，以及在实际问题中如何灵活运用递归和队列等数据结构。同时，这也是准备面试和提升编程能力的有效途径。在LeetCode上不断挑战自己，可以让我们更好地掌握各种算法，提高编程技能。