当前位置:网站首页>Interview Question 04.12. Summation Path-dfs+Auxiliary Array Method
Interview Question 04.12. Summation Path-dfs+Auxiliary Array Method
2022-08-10 18:33: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]
The code for solving this problem is as follows,Still a good topic,It is recommended not to use the brute force solution directly:
/** * 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;
}
边栏推荐
- 6月各手机银行活跃用户较快增长,创半年新高
- ZLMediaKit 服务器源码解读---RTSP推流拉流
- EasyGBS连接mysql数据库提示“can’t connect to mysql server”,如何解决?
- 剖析Framework面试—>>>冲击Android高级职位
- pip install fatal error C1083 cannot open include file "io.h" No such file or directory
- 剑指 Offer II 034. 外星语言是否排序-辅助数组法
- [JMeter]Beanshell解析Json格式的接口响应数据
- zabbix配置触发器
- JSON serialization and deserialization using Jackson API in Scala
- 如何通过JMobile软件实现虹科物联网HMI/网关的报警功能?
猜你喜欢
老板加薪!看我做的WPF Loading!!!
HarmonyOS自动化测试框架—Hypium
【严重】Nps 鉴权绕过 0day 漏洞
LeetCode 198:打家劫舍
【HMS core】【FAQ】Account Kit、push Kit典型问题合集1
Product Description丨MobPush fast integration method on Android side
Toronto Research Chemicals萜烯分析丨反式植物醇
Interface test advanced interface script using -apipost (pre/post execution script)
IoU、GIoU、DIoU、CIoU四种损失函数总结
接口测试进阶接口脚本使用—apipost(预/后执行脚本)
随机推荐
企业如何通过北森HR SaaS 自动化管理员工账号生命周期
pyspark columns merge into one row
文档标题能否支持公式
微服务架构-实现技术之六大基础组件:服务通信+事件驱动+负载均衡+服务路由+API网关+配置管理
机器人控制器编程实践指导书旧版-实践八 机器人综合设计
【测试】黑盒测试用例设计方法
「业务架构」业务能力的热图是什么,有啥用?
海思HI3516DV300开发资料
【FAQ】【Push Kit】 华为怎么设置角标
电路板ROHS测试报告怎么办理?电路板ROHS检测流程
Toronto Research Chemicals萜烯分析丨(+)-柠檬烯
ZLMediaKit 服务器源码解读---RTSP推流拉流
「企业架构」什么是Zachman框架?
Intelligent bid strategy how to affect advertising effectiveness?
LeetCode 198:打家劫舍
「Web应用架构」轮询,SSE 和WebSocket,如何选择合适的?
pip install fatal error C1083 cannot open include file "io.h" No such file or directory
去除富文本标签样式
php7中使用“??”运算符
MySQL数据高级查询之连接查询、联合查询、子查询[通俗易懂]