当前位置:网站首页>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;
}
边栏推荐
猜你喜欢
运维如何学习、自我提升价值?
Allegro软件Shape菜单下的每个命令的含义
【FAQ】【Push Kit】推送服务,回执配置一直报错、回执过期修改、怎么删除配置的回执
Toronto Research Chemicals萜烯分析丨(+)-柠檬烯
类型和id对应的两个数组
【HMS core】【FAQ】AR Engine、Analytics Kit、Video Editor Kit、Image Kit、Map Kit典型问题合集2
Mysql索引、事务与存储引擎
报告详解影响英特尔10/11/12代酷睿处理器的ÆPIC Leak安全漏洞
【HMS core】【FAQ】Analytics Kit、Push Kit典型问题合集3
剖析Framework面试—>>>冲击Android高级职位
随机推荐
zabbix配置触发器
eager模式和graph模式 Tensorflow
go语言的性能基准测试、性能优化测试和性能调优
定时器循环展示数组
How to choose Fengjiawei PHY62xx series?PHY6222/PHY6212/PHY6252
Before opening a futures account, you must confirm the handling fee as soon as possible
【深度学习21天学习挑战赛】4、初尝循环神经网络(RNN)——股票预测
三坐标雷达显示软件 SPx Viewer-3D
flex使用align-content无效
ZLMediaKit 服务器源码解读---RTSP推流拉流
FFmpeg extract H264 nalu from the mp4
[Image segmentation] Image segmentation based on cellular automata with matlab code
MySql主要性能指标说明
多线程与高并发(五)—— 源码解析 ReentrantLock
入门:人脸专集2 | 人脸关键点检测汇总(文末有相关文章链接)
Making Pre-trained Language Models Better Few-Shot Learners
开源一夏 | mysql5.7 安装部署 -二进制安装
电路板ROHS测试报告怎么办理?电路板ROHS检测流程
Selenium - 如何操作鼠标进行悬停、右击、双击、拖拽?
c语言进阶篇:柔性数组