当前位置: 首页 > article >正文

【leetcode hot 100 437】路径总和Ⅲ

解法一:(深度优先搜索)穷举所有的可能 =》访问每一个节点 node,检测以 node 为起始节点且向下延深的路径有多少种。递归遍历每一个节点的所有可能的路径,然后将这些路径数目加起来即为返回结果。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if(root==null){
            return 0;
        }

        int res = rootSum(root, targetSum);
        res += pathSum(root.left, targetSum);
        res += pathSum(root.right, targetSum);
        return res;
    }

    public int rootSum(TreeNode root, int targetSum){
        if(root==null){
            return 0;
        }
        int res = 0;
        if(root.val==targetSum){
            res++;
        }
        res += rootSum(root.left, targetSum-root.val);
        res += rootSum(root.right, targetSum-root.val);
        return res;
    }
}

注意:

  • public int pathSum(TreeNode root, int targetSum):根节点+左节点+右节点分开单独遍历每一个节点的所有可能的路径;public int rootSum(TreeNode root, int targetSum)遍历根节点所有可能的路径。
  • pathSum(TreeNode root, int targetSum)rootSum(TreeNode root, int targetSum)int改为long可以解决下述问题。
    在这里插入图片描述

http://www.kler.cn/a/590429.html

相关文章:

  • CC44.【C++ Cont】哈希表的模拟实现
  • 利用github部署项目
  • 跨平台直播美颜SDK开发指南:如何兼容iOS、Android与Web
  • (笔记)Ubuntu 20编译Linux 4.19.262内核
  • Java创造型模式之原型模式详解
  • 基于 Docker 和 Flask 构建高并发微服务架构
  • uni-app+SpringBoot: 前端传参,后端如何接收参数
  • 解决git init 命令不显示.git
  • [特殊字符] 深度实战:Android 13 系统定制之 Recovery 模式瘦身指南
  • C++笔记-类和对象(下)
  • 苹果计划为 AirPods 配备实时对话翻译功能,或随 iOS 19 上线
  • 鸿蒙开发:什么是ArkTs?
  • 用旧的手机搭建 MQTT Broker-Node_red
  • 【Linux系列】文件压缩
  • 【前端效果】CSS实现动态渐变背景动画
  • 前端面试:babel-runtime 作用是啥?
  • 信创环境下TOP5甘特图工具对比:从功能到适配性测评
  • 蓝桥杯Python赛道备赛——Day7:动态规划(基础)
  • C++ map set pair
  • 《论分布式系统架构设计及其应用》架构师论文