当前位置:网站首页>面试题 04.12. 求和路径-dfs+辅助数组法
面试题 04.12. 求和路径-dfs+辅助数组法
2022-08-10 18:00:00 【Mr Gao】
面试题 04.12. 求和路径
给定一棵二叉树,其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法,打印节点数值总和等于某个给定值的所有路径的数量。注意,路径不一定非得从二叉树的根节点或叶节点开始或结束,但是其方向必须向下(只能从父节点指向子节点方向)。
示例:
给定如下二叉树,以及目标和 sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
3
解释:和为 22 的路径有:[5,4,11,2], [5,8,4,5], [4,11,7]
此题解题代码如下,还是不错的一个题目,建议不要直接使用暴力解法:
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */
int count;
void dfs(struct TreeNode*root,int sum,int val,int *r,int h){
if(root){
r[h]=root->val;
if(root->left){
dfs(root->left,sum,root->val+val,r,h+1);
}
if(root->right){
dfs(root->right,sum,root->val+val,r,h+1);
}
int eval=root->val+val;
if(eval==sum){
count++;
}
for(int i=0;i<h;i++){
eval=eval-r[i];
if(eval==sum){
count++;
}
}
}
}
int pathSum(struct TreeNode* root, int sum){
int *r=(int *)malloc(sizeof(int)*1000);
count=0;
dfs(root,sum,0,r,0);
return count;
}
边栏推荐
- Selenium - 如何使用隐式、显示、强制元素等待?
- AVFrame相关api内存管理
- 设置iptables规则来保护CS服务器
- 测试接口出现“data“: “Full authentication is required to access this resource“凭证已过期
- 网络可观测性:让您的网络监控更上一层楼|TechGenix
- 直播回顾|多云时代,如何建设企业级云管理平台?(附建设指南下载)
- EasyGBS连接mysql数据库提示“can’t connect to mysql server”,如何解决?
- H3C_堆叠(IRF)及链路聚合在项目中的综合应用
- 海思HI3516DV300开发资料
- 关于技术分享的思考
猜你喜欢
Allegro软件Shape菜单下的每个命令的含义
CSV(Comma-Separate-Values)逗号分隔值文件
【HMS core】【FAQ】AR Engine、Analytics Kit、Video Editor Kit、Image Kit、Map Kit典型问题合集2
不能直接在交易所期货开户
产品-Axure9英文版,A页面内a1状态跳转B页面的b2状态,(条件跳转状态)
【图像分割】基于元胞自动机实现图像分割附matlab代码
[Image segmentation] Image segmentation based on cellular automata with matlab code
破解校园数字安全难点,联想推出智慧教育安全体系
HarmonyOS自动化测试框架—Hypium
机器人控制器编程实践指导书旧版-实践三 直流电机(执行器)
随机推荐
Product Description丨MobPush fast integration method on Android side
开发模式对测试的影响
Keil5退出仿真调试卡死的解决办法
接口测试进阶接口脚本使用—apipost(预/后执行脚本)
Colocate Join :ClickHouse的一种高性能分布式join查询模型
智能出价策略如何影响广告效果?
【HMS core】【FAQ】Analytics Kit、Push Kit典型问题合集3
高手问答第 290 期 —— SaaS产品经理从菜鸟到专家
电路板ROHS测试报告怎么办理?电路板ROHS检测流程
迪文发布新款2K高清DGUS智能屏
【FAQ】【Push Kit】推送服务,回执配置一直报错、回执过期修改、怎么删除配置的回执
c语言进阶篇:柔性数组
go语言的性能基准测试、性能优化测试和性能调优
不止跑路,拯救误操作rm -rf /*的小伙儿
钻石价格预测的ML全流程!从模型构建调优道部署应用!
Toronto Research Chemicals BTK甜味剂配方丨D-Abequose
20220810
oracle11g体系结构
Toronto Research Chemicals BTK抑制剂丨ACP-5197
21天打卡挑战学习MySQL——《MySQL表管理》第二周 第五篇