登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

豆瓜网 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 科技 ›【LeetCode 437】算法：路径总和 III

【LeetCode 437】算法：路径总和 III

驼娑 4 天前
题目：给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
1.png

核心思想：
这个问题的核心思想是深度优先搜索（DFS）结合递归。从二叉树的根节点开始，递归地遍历每个节点，并在遍历过程中计算从当前节点到任意叶子节点的路径和。如果路径和等于目标和 targetSum，则计数器加一。为了实现这一点，需要维护一个当前路径的和，并在遍历过程中更新它。
算法步骤：

  • 定义辅助函数：定义一个辅助函数 findPaths，它接受当前节点和目标和 targetSum 作为参数，用于计算以当前节点为起点，路径和为 targetSum 的路径数量。
  • 递归终止条件：如果当前节点为空，返回 0，因为没有路径。
  • 初始化计数器：对于每个节点，初始化计数器 count 为 0。
  • 检查叶子节点：如果当前节点是叶子节点（即没有左右子节点），检查当前节点的值是否等于 targetSum，如果是，则 count 加一。
  • 递归遍历子树：递归地调用 findPaths 函数遍历当前节点的左右子树，并将当前节点的值从 targetSum 中减去，因为路径和需要从当前节点开始计算。
  • 累加结果：在主函数 pathSum 中，递归地调用自身来遍历左子树和右子树，并将结果累加到 count 中。
  • 返回结果：返回 count 作为最终结果。
复杂度分析：
时间复杂度：O(N)，其中 N 是二叉树中节点的数量。需要访问每个节点一次来计算路径和。
空间复杂度：O(H)，其中 H 是二叉树的高度。这是因为递归调用的深度最多为树的高度。
Java代码实现：
  1. class Solution {
  2.     int count = 0;
  4.     public int pathSum(TreeNode root, int targetSum) {
  5.         if (root == null) {
  6.             return 0;
  7.         }
  8.         count += findPaths(root, targetSum);
  9.         count += pathSum(root.left, targetSum);
  10.         count += pathSum(root.right, targetSum);
  11.         return count;
  12.     }
  14.     private int findPaths(TreeNode node, int targetSum) {
  15.         if (node == null) {
  16.             return 0;
  17.         }
  18.         int count = 0;
  19.         if (node.val == targetSum) {
  20.             count++;
  21.         }
  22.         if (node.left != null) {
  23.             count += findPaths(node.left, targetSum - node.val);
  24.         }
  25.         if (node.right != null) {
  26.             count += findPaths(node.right, targetSum - node.val);
  27.         }
  28.         return count;
  29.     }
  30. }
复制代码
来源：豆瓜网用户自行投稿发布，如果侵权，请联系站长删除
LeetCode算法路径总和III

使用道具 举报

相关推荐
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
驼娑
4 天前

0

粉丝关注

16

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫