面试热题(路径总和II)

给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

 在这里给大家提供两种方法进行思考,第一种方法是递归,第二种方式使用回溯的方式进行爆搜

        递归:树具有天然的递归结构,将一个大的问题转换成多个相同的子问题而进行解决,就相当于你会0-1的算式,你自然而然可以推导出0-n的算式(递归终止条件+递归操作

       我觉的这个图可以很形象的说明一些问题,通过改变每个结点的差值,最后进行叶子结点与传入的target进行比较,如果相等,就说明树中肯定有满足情况的路径

解题步骤:

  • 方法中返回什么,我们就创建什么
 public List<List<Integer>> pathSum(TreeNode root, int targetSum) {List<List<Integer>> resList=new LinkedList<>();...}
  • 递归结束的条件(分为第一次入参和叶子结点的入参,两者的操作不一样)
        //如果传进行的叶子结点为空,直接返回一个空链表if(root==null){return resList;}//如果是叶子结点且叶子结点的值等于target,则该叶子结点是满足情况下的一条路径上的值if(root.left==null&&root.right==null){if(root.val==targetSum){List<Integer> list=new LinkedList<>();list.add(root.val);//将该路径加入总结果集中resList.add(list);}return resList;}
  • 每次递归的时候将target-root.val作为参数传下去
int diff=targetSum-root.val;
  • 如果左树不为空,递归左树,如果右树不为空,递归右树
        if(root.left!=null){List<List<Integer>> curList=pathSum(root.left,diff);for(int i=0;i<curList.size();i++){List<Integer> list1=curList.get(i);//将该节点加入路径中list1.add(0,root.val);//加入到结果集中resList.add(list1);}}if(root.right!=null){List<List<Integer>> curList=pathSum(root.right,diff);for(int i=0;i<curList.size();i++){List<Integer> list1=curList.get(i);list1.add(0,root.val);resList.add(list1);}}
  • 最后每次递归结束后返回结果集,供归的时候进行使用
return resList;

方法二:回溯 

回溯的方法相当于暴力搜索一样,但是对于面试而言,我更加推荐回溯(比较容易记忆)

    //大体思想其实和递归差不多,就是回溯这种题有个特定的模板,有的时候,即使你不会做,那你也有可能把题做出来List<List<Integer>> resList=new LinkedList<>();List<Integer> path=new LinkedList<>();public List<List<Integer>> pathSum(TreeNode root, int targetSum) {if(root==null){return resList;}backtracing(root,targetSum);return resList;}public void backtracing(TreeNode root,int targetSum){if(root==null){return;}path.add(root.val);if(targetSum==root.val&&root.left==null&&root.right==null){resList.add(new ArrayList<>(path));}int diff=targetSum-root.val;if(root.left!=null){pathSum(root.left,diff);//回溯path.remove(path.size()-1);}if(root.right!=null){pathSum(root.right,diff);path.remove(path.size()-1);}}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/83317.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

博客网站添加复制转载提醒弹窗Html代码

网站如果是完全禁止右键&#xff08;复制、另存为等&#xff09;操作&#xff0c;对用户来说体验感会降低&#xff0c;但是又不希望自己的原创内容直接被copy&#xff0c;今天飞飞和你们分享几行复制转载提醒弹窗Html代码。 效果展示&#xff1a; 复制以下代码&#xff0c;将其…

Linux--core dump打开的情况下,运行下面的代码,会发生什么?

代码&#xff1a; #include <iostream> #include <signal.h> #include <unistd.h>using namespace std;void catchSig(int signum) {cout<< "进程捕捉到了一个信号&#xff0c;正在处理中&#xff1a; "<< signum << " p…

开发工具Eclipse的使用之导入项目(import)

&#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 接下来看看由辉辉所写的关于Eclipse使用的相关操作吧 一.导读 上篇我们已经详细介绍了开发工具eclipse&#xff0c;也说明了eclipse的基本使用&#xff0c;那么我们这篇来详细讲述一下怎…

docker基本使用方法

docker使用 1. Docker 介绍 Docker 可以让开发者打包他们的应用以及依赖包到一个轻量级、可移植的容器中&#xff0c;然后发布到任何流行的 Linux 机器上&#xff0c;也可以实现虚拟化。Docker 使您能够将应用程序与基础架构分开&#xff0c;从而可以快速交付软件。通过利用 …

springcloud3 bus+springconfig 实现配置文件的动态刷新(了解)

一 springcloud Bus的作用 1.1 springcloud的作用 spring cloud bus是用来将分布式系统的节点与轻量级消息系统链接起来的框架。 它整合了java的事件处理机制和消息中间件的功能。其中目前支持RabbitMQ和kafka 简介&#xff1a; bus实现多个服务的配置文件动态刷新。 1.2 …

DC电源模块在工业控制器中的重要性

BOSHIDA DC电源模块在工业控制器中的重要性 DC电源模块在工业控制器中起着非常重要的作用&#xff0c;它是实现工业控制器运转所必需的组成部分。 DC电源模块主要用于将交流电转换成直流电供给工业控制器中的各个部件&#xff0c;包括控制器内部的微处理器、传感器、执行器等等…

【SpringCloud】RabbitMQ基础

1.初识MQ 1.1.同步和异步通讯 微服务间通讯有同步和异步两种方式&#xff1a; 同步通讯&#xff1a;就像打电话&#xff0c;需要实时响应。 异步通讯&#xff1a;就像发邮件&#xff0c;不需要马上回复。 两种方式各有优劣&#xff0c;打电话可以立即得到响应&#xff0c;…

如何系列 如何使用Resilience4j提高应用弹性和容错

文章目录 背景简介Maven重试器注解式编程式配置事件监听指标监控健康检查 速率限制注解式编程式配置事件监听指标监控动态修改配置 断路器注解式配置 舱壁注解式 时间限制器多组件配合使用最佳实践 配置参考&#xff1a; 背景 在应用程序开发的过程中&#xff0c;特别是在构建…

机器学习基础

什么是机器学习&#xff1f;----本质就是寻找一个函数。 可以训练什么样的函数呢&#xff1f; 可以训练一个回归的函数&#xff0c;也可以训练一个分类的函数。 这个例子的需要分类的类别是19*19的选项。 在机器学习领域里面不止回归和分类。 举例&#xff1a;预测函数 利用已…

Llama 2 with langchain项目详解(一)

Llama 2 with langchain项目详解(一) 2023年2月25日,美国Meta公司发布了Llama 1开源大模型。随后,于2023年7月18日,Meta公司发布了Llama 2开源大模型,该系列包括了70亿、130亿和700亿等不同参数规模的模型。相较于Llama 1,Llama 2的训练数据增加了40%,上下文长度提升至…

Oracle数据迁移

问题描述&#xff1a; oracle数据库的所有表结构、数据、索引等需要需从测试库迁移到正式库。 解决步骤&#xff1a; oracle数据库迁移&#xff0c;主要通过expdp从测试库所在的源服务器将指定的数据表或数据源导出为一个或多个数据文件&#xff08;.dmp文件&#xff09;&…

MySql用户管理、权限管理

用户管理 1. 查看系统用户&#xff08;查询mysql系统数据库中的user表&#xff09; select * from mysql.user; 2. 创建用户 CREATE USER 用户名主机名 identified by 密码 -- 创建用户zhonghua,只能在当前主句localhost访问,密码为123456 create user zhonghualocalhost i…

Fabric系列 - 知识点整理

知识点 源码编译 主机编译 容器编译 手动部署(docker-compose) 单peer 多peer 中途加peer 多主机多peer 链码 语法, 接口 (go版) 命令行调用 ca server 在DApp中使用SDK调用 (js版) 部署的几个阶段 部署1排序和1节点, 1组织1通道 光部署能Dapp 带ca server (每个组织一个)…

使用IIS服务器部署Flask python Web项目

参考文章 ""D:\Program Files (x86)\Python310\python310.exe"|"D:\Program Files (x86)\Python310\lib\site-packages\wfastcgi.py"" can now be used as a FastCGI script processor参考文章 请求路径填写*&#xff0c;模块选择FastCgiModule&…

Android使用kotlin+协程+room数据库的简单应用

前言&#xff1a;一般主线程&#xff08;UI线程&#xff09;中是不能执行创建数据这些操作的&#xff0c;因为等待时间长。所以协程就是为了解决这个问题出现。 第一步&#xff1a;在模块级的build.gradle中引入 id com.android.application// roomid kotlin-androidid kotlin…

kafka-2.12使用记录

kafka-2.12使用记录 安装kafka 2.12版本 下载安装包 根据你的系统下载rpm /deb /zip包等等, 这里我使用的是rpm包 安装命令 rpm -ivh kafka-2.12-1.nfs.x86_64.rpm启动内置Zookeeper 以下命令要写在同一行上 /opt/kafka-2.12/bin/zookeeper-server-start.sh /opt/kafka-2…

【前端 | CSS】align-items与align-content的区别

align-items 描述 CSS align-items 属性将所有直接子节点上的 align-self 值设置为一个组。align-self 属性设置项目在其包含块中在交叉轴方向上的对齐方式 align-items是针对每一个子项起作用&#xff0c;它的基本单位是每一个子项&#xff0c;在所有情况下都有效果&…

【云原生-Uptime Kuma】自动化运维监控工具-Uptime Kuma

文章目录 简介基础信息开源信息 在线安装docker安装Uptime Kuma安装docker-compose安装 在线访问账号创建基础配置 监控管理监控看板添加监控组配置http监控监控异常通知消息 自定义监控页面特性支持支持计划维护特性总结 总结 简介 基础信息 uptime-kuma是一款开源的、多功能…

ChatGLM-RLHF(六)-PPO(Proximal Policy Optimization)原理实现代码逐行注释

一&#xff0c;前言 从open AI 的论文可以看到&#xff0c;大语言模型的优化&#xff0c;分下面三个步骤&#xff0c;SFT&#xff0c;RM&#xff0c;PPO&#xff0c;我们跟随大神的步伐&#xff0c;来学习一下这三个步骤和代码实现&#xff0c;本章介绍PPO代码实现。 上章我们…

无线液位传感器—简介

近年来&#xff0c;随着无线传感网络技术的愈发成熟和稳定&#xff0c;无线传感器因其安装、维护方便&#xff0c;不用布线、节约成本&#xff0c;监测方便&#xff0c;使用灵活&#xff0c;可适用于多种工业领域等优点&#xff0c;正在逐步替代部分传统有线传感器&#xff0c;…