九度OJ → 题目1368:二叉树中和为某一值的路径 ← DFS

【题目来源】
由于九度OJ(
http://ac.jobdu.com/)已经永久关闭,故无法在其上进行在线提交代码。
幸运的是,在AcWing上有此题目“二叉树中和为某一值的路径”,但描述有些不同。可详见:
https://www.acwing.com/problem/content/description/45/

【题目描述】
输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。
路径定义为
从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

【输入描述】
每个测试案例包括 n+1 行:
第一行为 2 个整数 n,k(1<=n<=10000),n 表示结点的个数,k 表示要求的路径和,结点编号 id 从 1 到 n 。
接下来有 n 行(
第 i 行表示第 i 个结点的信息,i=1~n)。这 n 行中每行为 3 个整数 vi, leftnode, rightnode,vi 表示第 i 个结点的值,leftnode 表示第 i 个结点的左孩子结点编号,rightnode 表示第 i 个结点的右孩子结点编号,若无结点值为 -1。编号为 1 的结点为根结点

【输出描述】
对应每个测试案例,先输出“result:”占一行,接下来按
字典顺序输出满足条件的所有路径,这些路径由结点编号组成,输出格式参照输出样例。

【测试样例】
输入样例:
5 22
10 2 3
5 4 5
12 -1 -1
4 -1 -1
7 -1 -1

1 5
1 -1 -1

输出样例:
result:
A path is found: 1 2 5
A path is found: 1 3
result:

【算法分析】
** vector的
pop_back() 函数的作用是弹出 vector 中的最后一个元素
若要深入理解本例中的 pop_back() 函数的作用,可将样例绘制为示意图后,按示意图模拟执行代码,便可直观顿悟。本题样例的图示如下:

** 由于输出需要按字典顺序输出满足条件的所有路径,所以在代码中需要对左右结点编号进行交换排序。代码如下:

if(p[i].lchild>p[i].rchild) {int t=p[i].lchild;p[i].lchild=p[i].rchild;p[i].rchild=t;
}

** AcWing 上关于此题是用实现的,参考代码如下:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {public:vector<vector<int>> ans;vector<int> path;vector<vector<int>> findPath(TreeNode* root,int sum){dfs(root,0,sum);return ans;}void dfs(TreeNode *root,int sum,int target){if(!root) return;path.push_back(root->val);sum+=root->val;if(!root->left && !root->right){if(sum==target) ans.push_back(path);} else{if(root->left) dfs(root->left,sum,target);if(root->right) dfs(root->right,sum,target);}path.pop_back();}
};

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int maxn=1e3+5;
struct Node {int value,lchild,rchild;
} p[maxn];vector<int> ans;void dfs(int cur,int sum,int id) {if(id==-1) return;if(sum==cur+p[id].value && p[id].lchild==-1 && p[id].rchild==-1) {ans.push_back(id);printf("A path is found:");for(int i=0; i<ans.size(); i++) printf(" %d",ans[i]);printf("\n");ans.pop_back();return;}if(sum>cur+p[id].value) {ans.push_back(id);dfs(cur+p[id].value,sum,p[id].lchild);dfs(cur+p[id].value,sum,p[id].rchild);ans.pop_back();}
}int main() {int n,tot;while(scanf("%d %d",&n,&tot)!=EOF) {ans.clear();for(int i=1; i<=n; i++) {scanf("%d %d %d",&p[i].value,&p[i].lchild,&p[i].rchild);if(p[i].lchild>p[i].rchild) {int t=p[i].lchild;p[i].lchild=p[i].rchild;p[i].rchild=t;}}printf("result:\n");dfs(0,tot,1);}return 0;
}/*
in:
5 22
10 2 3
5 4 5
12 -1 -1
4 -1 -1
7 -1 -1
1 5
1 -1 -1out:
result:
A path is found: 1 2 5
A path is found: 1 3
result:
*/



【参考文献】
https://www.cnblogs.com/llguanli/p/6951966.html

https://blog.csdn.net/qq_32867925/article/details/104851126





 

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

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

相关文章

redis 集群 1:李代桃僵 —— Sentinel

目前我们讲的 Redis 还只是主从方案&#xff0c;最终一致性。读者们可思考过&#xff0c;如果主节点凌晨 3 点突发宕机怎么办&#xff1f;就坐等运维从床上爬起来&#xff0c;然后手工进行从主切换&#xff0c;再通知所有的程序把地址统统改一遍重新上线么&#xff1f;毫无疑问…

绿色项目管理:为环境和效益双赢

绿色项目管理&#xff1a;为环境和效益双赢 在21世纪的今天&#xff0c;我们正面临着各种全球性的环境问题&#xff0c;从气候变化到资源枯竭。作为项目经理&#xff0c;我们有责任和机会确保我们的项目对环境的影响最小&#xff0c;并在可能的情况下为环境做出积极的贡献。 …

P9503 『MGOI』Simple Round I | B. 魔法照相馆

题目背景 照片留下了值得留恋的瞬间&#xff0c;但对于魔法士来说最重要的是向前看。——殿堂魔法士 W 题目描述 小 M 正在准备入学所必需的魔法士证件&#xff0c;因此他来到了纵深巷的魔法照相馆。 在等待的时候&#xff0c;小 M 注意到魔法照相馆有三个幕布&#xff0c;颜…

建筑行业是不是一个夕阳产业?一建值得考吗?

建筑行业行业是不是夕阳产业&#xff0c;提出这个问题的人已经了解了现在建筑行业的不景气&#xff0c;从3年疫情到放开疫情管控&#xff0c;2023年是疫情放开后最好的一年。 建筑上下游各产业链行业失业率攀升&#xff0c;房屋建筑土地没人卖&#xff0c;多修建公共建筑&…

RISC-V公测平台发布:如何在SG2042上玩转OpenMPI

About HS-2 HS-2 RISC-V通用主板是澎峰科技与合作伙伴共同研发的一款专为开发者设计的标准mATX主板&#xff0c;它预装了澎峰科技为RISC-V高性能服务器定制开发的软件包&#xff0c;包括各种标准bencmark、支持V扩展的GCC编译器、计算库、中间件以及多种典型服务器应用程序。…

音频客观感知MOS对比,对ViSQOL、PESQ、MosNet(神经网络MOS分)和polqa一致性对比和可信度验证

原创&#xff1a;转载需附链接&#xff1a; https://blog.csdn.net/qq_37100442/article/details/132057139?spm1001.2014.3001.5502 一、背景 Mos分评价音质重要指标&#xff0c;最近也有很多机构和公司在研究适合自己的评价体系。目前Mos分主要分为主观评测和客观感知评价。…

6.6 实现卷积神经网络LeNet训练并预测手写体数字

模型架构 代码实现 import torch from torch import nn from d2l import torch as d2lnet nn.Sequential(nn.Conv2d(1,6,kernel_size5,padding2),nn.Sigmoid(),#padding2补偿5x5卷积核导致的特征减少。nn.AvgPool2d(kernel_size2,stride2),nn.Conv2d(6,16,kernel_size5),nn.S…

黑马大数据学习笔记5-案例

目录 需求分析背景介绍目标需求数据内容DBeaver连接到Hive建库建表加载数据 ETL数据清洗数据问题需求实现查看结果扩展 指标计算需求需求指标统计 可视化展示BIFineBI的介绍及安装FineBI配置数据源及数据准备 可视化展示 P73~77 https://www.bilibili.com/video/BV1WY4y197g7?…

宋浩概率论笔记(三)随机向量/二维随机变量

第三更&#xff1a;本章的内容最重要的在于概念的理解与抽象&#xff0c;二重积分通常情况下不会考得很难。此外&#xff0c;本次暂且忽略【二维连续型随机变量函数的分布】这一章节&#xff0c;非常抽象且难度较高&#xff0c;之后有时间再更新。

回归决策树模拟sin函数

# -*-coding:utf-8-*- import numpy as np from sklearn import tree import matplotlib.pyplot as pltplt.switch_backend("TkAgg") # 创建了一个随机数生成器对象 rng rngnp.random.RandomState(1) print("rng",rng) #5*rng.rand(80,1)生成一个80行、1列…

恒盛策略:上交所过户费收费标准?

随着我国股市的发展&#xff0c;股票买卖所的过户费成为了广阔投资者关注的焦点之一。在我国股票商场中&#xff0c;上交所是最重要的买卖所之一&#xff0c;因而上交所过户费的收费规范备受到了广泛关注。那么&#xff0c;上交所过户费的收费规范究竟怎么拟定&#xff1f;对投…

【Docker】Docker私有仓库的使用

目录 一、搭建私有仓库 二、上传镜像到私有仓库 三、从私有仓库拉取镜像 一、搭建私有仓库 首先我们需要拉取仓库的镜像 docker pull registry 然后创建私有仓库容器 docker run -it --namereg -p 5000:5000 registry 这个时候我们可以打开浏览器访问5000端口看是否成功&…

python-opencv对极几何 StereoRectify

OpenCV如何正确使用stereoRectify函数 函数介绍 用于双目相机的立体校正环节中&#xff0c;这里只谈谈这个函数怎么使用&#xff0c;参数具体指哪些函数参数 随便去网上一搜或者看官方手册就能得到参数信息&#xff0c;但是&#xff01;&#xff01;相对关系非常容易出错&…

【MySQL】事务的多版本并发控制(MVCC)

目录 一、数据库并发的三种场景二、MVCC2.1 三个记录隐藏字段2.2 undo log&#xff08;撤销日志&#xff09;2.3 模拟MVCC2.3.1 模拟更新&#xff08;update&#xff09;2.3.1 模拟删除&#xff08;delete&#xff09;2.3.1 模拟插入&#xff08;insert&#xff09;2.3.1 模拟查…

maven中常见问题

文章目录 一、配置项提示二、父子打包三、打包之后不显示target四、自定义打包之后的jar包名称五、整个项目打包5.1、父项目管理插件和微服务打包 一、配置项提示 SpringBoot中提示错误信息 表示的是SpringBoot中的注释提示没有配置&#xff01;那么可以来使用一下springboot官…

安全学习DAY14_JS信息打点

信息打点——前端JS框架 文章目录 信息打点——前端JS框架小节概述-思维导图JS安全概述什么是JS渗透测试&#xff1f;前后端差异JS安全问题流行的Js框架如何判定JS开发应用&#xff1f; 测试方法&#xff08;JS文件的获取以及分析方法1、手工搜索分析2、半自动Burp分析插件介绍…

problem(3):python IDE和python解释器

为什么写这篇文章呢&#xff1f;遇到了下面的问题&#xff0c;相同的解释器&#xff0c;如果运行angr库的代码&#xff0c;会出现 这样的情况&#xff0c;但是用spyder IDE 会显示正常&#xff0c;很奇怪 应该就是IDE的原因 IDE的循环导入问题 检查IDE配置&#xff1a; 如果可…

引流精准客源方法,学会这一招就够你用的了

科思创业汇 大家好&#xff0c;这里是科思创业汇&#xff0c;一个轻资产创业孵化平台。赚钱的方式有很多种&#xff0c;我希望在科思创业汇能够给你带来最快乐的那一种&#xff01; 第一&#xff0c;你要想一想&#xff0c;你想吸引什么样的人&#xff1f; 您的排水目的是推…

构建语言模型:BERT 分步实施指南

学习目标 了解 BERT 的架构和组件。了解 BERT 输入所需的预处理步骤以及如何处理不同的输入序列长度。获得使用 TensorFlow 或 PyTorch 等流行机器学习框架实施 BERT 的实践知识。了解如何针对特定下游任务(例如文本分类或命名实体识别)微调 BERT。为什么我们需要 BERT? 正…

Vue3+SpringBoot快速开发模板

起因&#xff1a;个人开发过程经常会使用到Vue3SpringBoot技术栈来开发项目&#xff0c;每次在项目初始化时都需要涉及一些重复的整理工作&#xff0c;于是结合一些个人觉得不错的前后端模板进行整合&#xff0c;打通一些大多数项目都需要的实现的基础功能&#xff0c;以便于快…