当前位置:网站首页>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;
}
边栏推荐
猜你喜欢
报告详解影响英特尔10/11/12代酷睿处理器的ÆPIC Leak安全漏洞
【快应用】如何使用命令打包快应用rpk
测试接口出现“data“: “Full authentication is required to access this resource“凭证已过期
机器人控制器编程实践指导书旧版-实践七 无线通信(网络)
CSV(Comma-Separate-Values)逗号分隔值文件
go语言的性能基准测试、性能优化测试和性能调优
直播回顾|多云时代,如何建设企业级云管理平台?(附建设指南下载)
装饰者模式
Toronto Research Chemicals霉菌毒素分析丨T2 四醇
老板加薪!看我做的WPF Loading!!!
随机推荐
【HMS core】【FAQ】Analytics Kit、Push Kit典型问题合集3
ZLMediaKit 服务器源码解读---RTSP推流拉流
文档标题能否支持公式
设置iptables规则来保护CS服务器
Toronto Research Chemicals农药检测丨甲硫威
Making Pre-trained Language Models Better Few-Shot Learners
测试接口出现“data“: “Full authentication is required to access this resource“凭证已过期
面试题 04.12. 求和路径-dfs+辅助数组法
const的自己理解
Thoughts on Technology Sharing
「业务架构」业务能力的热图是什么,有啥用?
让mixin为项目开发助力【及递归优化新尝试】
pyspark columns merge into one row
20220810
6-11 Preorder output leaf nodes (15 points)
pip3升级到22.2.2
海思HI3516DV300开发资料
CSV(Comma-Separate-Values)逗号分隔值文件
D-Wave成功上市!量子计算商业化正在加速
requires ‘angle‘ attribute to be a multiple of 45