九度oj 题目1368:二叉树中和为某一值的路径
2024-10-19 17:29:53
- 题目描述:
-
输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
- 输入:
-
每个测试案例包括n+1行:
第一行为2个整数n,k(1<=n<=10000),n表示结点的个数,k表示要求的路径和,结点编号从1到n。
接下来有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: 考察数据结构,但题目中有许多坑。
一是按字典顺序输出。 用深搜顺序解决。
二是路径指的是根节点到叶子节点。 加上判断。 代码如下#include <cstdio>
#include <cstdlib>
#include <iostream> using namespace std; struct Node{
int value;
int left;
int right;
}; Node tree[]; int path[];
int n, k; void dfs(int n, int sum, int step) { int l = tree[n].left;
int r = tree[n].right; if(sum == k && l == - && r == -) {
printf("A path is found:");
for(int i = ; i < step; i++) {
printf(" %d",path[i]);
}
puts("");
return;
} int p1 = min(l,r);
int p2 = max(l,r); if(p1 != -) {
path[step] = p1;
int v = tree[p1].value;
dfs(p1, sum+v, step+);
}
if(p2 != -) {
path[step] = p2;
int v = tree[p2].value;
dfs(p2, sum+v, step+);
}
} int main(int argc, char const *argv[])
{
//freopen("input.txt","r",stdin);
while(scanf("%d %d",&n,&k) != EOF) {
for(int i = ; i <= n; i++) {
scanf("%d %d %d",&tree[i].value, &tree[i].left, &tree[i].right);
}
path[] = ;
int v = tree[].value;
puts("result:");
dfs(, v, ); }
return ;
}
最新文章
- LPC1769 CAN的自测试模式
- 在Mac OS X Yosemite 10.10.3 中搭建第一个 ASP.NET 5 Web 项目
- 使用awk排除第一行和第二行的数据
- jquery 常用函数集锦
- 51Nod 1201 整数划分 (经典dp)
- 3行3列表格 table实现,div+css实现
- 衬衫面料品牌:Alumo_衬衫_男装_男装:衬衫、法式衬衫、袖扣领带、西服西裤等男士正装服饰-仕族官网
- pthread_t结构的定义
- 多尺度二维离散小波分解wavedec2
- mysql、sqlserver数据库常见数据类型对应java中的的类型探究
- Swing-JTable的渲染器与编辑器使用demo
- 热门开源项目:Guns-后台管理系统
- input 和button的区别
- java创建线程的三种方法
- MacBook Air 装win10系统 by DODUI
- 线程同步-使用CountDownEvent类
- 【转】C# 的 IDisposable 接口
- Spark(八)JVM调优以及GC垃圾收集器
- [会装]Hive安装(基于mysql数据库)
- js验证手机号码,邮箱,qq号