树.递归.路径总和
2021-07-31 14:22:17
判断二叉树中是否存在根节点到叶子节点的路径总和等于目标值，可以通过递归方法实现。以下是详细的解答：
问题分析：
给定二叉树的根节点 root 和一个目标整数 targetSum，需要判断是否存在从根节点到叶子节点的路径，使得路径上所有节点值的和等于 targetSum。
叶子节点是指没有子节点的节点。
递归思路：
基本情况：如果当前节点为空，返回 false。
更新目标值：从 targetSum 中减去当前节点的值，表示剩余需要达到的目标和。
叶子节点检查：如果当前节点是叶子节点（即左右子节点均为空），检查剩余的目标和是否为0。如果是，则找到了一条有效路径。
递归检查左右子树：对左右子节点递归调用函数，检查是否存在满足条件的路径。
代码实现：
class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { if (root == null) return false; targetSum -= root.val; if (root.left == null && root.right == null) { return targetSum == 0; } return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum); }}代码解释：
基本情况处理：如果 root 为空，直接返回 false，因为空树不存在任何路径。
更新目标和：targetSum 减去当前节点的值，表示剩余需要匹配的和。
叶子节点检查：如果当前节点是叶子节点，检查 targetSum 是否为0。如果是，说明从根节点到该叶子节点的路径和等于初始 targetSum，返回 true。
递归调用：分别对左子树和右子树递归调用 hasPathSum，只要其中一条路径满足条件即可返回 true。
示例验证：
示例1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
路径 5->4->11->2 的和为 22，输出 true。
示例2：
输入：root = [1,2,3], targetSum = 5
没有路径的和为 5，输出 false。
示例3：
输入：root = [1,2], targetSum = 0
没有路径的和为 0，输出 false。
复杂度分析：
时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点最多被访问一次。
空间复杂度：O(h)，其中 h 是二叉树的高度。递归调用的栈空间取决于树的高度，最坏情况下（树为链状）为 O(n)。
通过递归方法，可以高效地判断二叉树中是否存在满足条件的路径。该方法简洁且易于理解，适用于大多数二叉树路径总和问题。
热门标签
