UVA548 Tree (二叉树的遍历)
You are to determine the value of the leaf node in a given binary tree that is the terminal node of a
path of least value from the root of the binary tree to any leaf. The value of a path is the sum of values
of nodes along that path.
Input
The input file will contain a description of the binary tree given as the inorder and postorder traversal
sequences of that tree. Your program will read two line (until end of file) from the input file. The first
line will contain the sequence of values associated with an inorder traversal of the tree and the second
line will contain the sequence of values associated with a postorder traversal of the tree. All values
will be different, greater than zero and less than 10000. You may assume that no binary tree will have
more than 10000 nodes or less than 1 node.
Output
For each tree description you should output the value of the leaf node of a path of least value. In the
case of multiple paths of least value you should pick the one with the least value on the terminal node.
Sample Input
3 2 1 4 5 7 6
3 1 2 5 6 7 4
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
255
255
Sample Output
1
3
255
【分析】嗯 开始学习二叉树了,感觉很难,这个代码不是很懂,感觉像是先通过中序遍历,后序遍历求出先序遍历,找到子叶点求和。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#include<functional>
#define mod 1000000007
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
const int N=;
const int M=;
char s[];
int v1[],v2[],top;
int min_sum,ans;
int init(char *s,int *v) {
int top=;
for(int i=; s[i]; i++) {
while(s[i]==' ')
i++;
v[top]=;
while(s[i]&&isdigit(s[i])) {
v[top]=v[top]*+s[i]-'';
i++;
}
top++;
if(!s[i]) break;
}
return top;
}
int find(int *v,int n,int c) {
for(int i=n-; i>=; i--)
if(v[i]==c)
return i;
return ;
}
void build(int n,int *v1,int *v2,int sum) {
if(n<=)
return ;
int p=find(v1,n,v2[n-]);
//printf("v2[n-1]=%d p=%d\n",v2[n-1],p);
sum+=v2[n-];
if(p<=&&n-p-<=) {
if(sum==min_sum)
ans=min(ans,v2[n-]);
else if(sum<min_sum) {
min_sum=sum;
ans=v2[n-];
}
return ;
}
build(p,v1,v2,sum);
build(n-p-,v1+p+,v2+p,sum);
} int main() {
while(gets(s)) {
int v;
init(s,v1);
gets(s);
top=init(s,v2);
ans=min_sum=;
build(top,v1,v2,);
printf("%d\n",ans);
}
return ;
}
最新文章
- javascript中的defer和async学习+javascript执行顺序
- Delphi 为什么它提示PCHAR是不安全的类型呢 Unsafe type &#39;PChar&#39;
- HTTP服务负载均衡总结
- Java基础02 方法与数据成员
- python实现变参
- linux执行sh报错:$’\r’: 未找到命令的解决
- Sql Server——查询(二)
- Python3基础知识之元组、集合、字典
- Docker系统四:Dcoker的镜像管理
- 11.20 正则表达式 断言(?=exp)
- https验证证书的三个级别
- GoldenGate使用SQLEXEC和GETVAL实现码表关联
- 【Qt5】Windows下配置程序的产品、公司、版权、版本号等详细信息
- iOS开发之--宏定义与const的区别及使用方法
- 谁说delphi没有IOCP库,delphi新的IOCP类库,开源中
- ensembl数据库的使用方法
- CF597C Subsequences 树状数组 + 动态规划
- Error while loading shared libraries: libpq.so.5: cannot open shared object file: No such file or directory
- 爬虫模拟登陆之formdata表单数据
- inotify监测实例
热门文章
- [BZOJ1449] [JSOI2009]球队收益 / [BZOJ2895] 球队预算
- MySQL里执行SHOW INDEX结果中Cardinality的含义
- [poj 3281]最大流+建图很巧妙
- spring 配置文件读取 mysql username报错
- Installing Jenkins to Centos Docker
- 转:RBAC权限控制
- Spring - IoC(7): 延迟实例化
- [bzoj3676][Apio2014]回文串——Manacher+后缀自动机+倍增
- jquery的ajax提交
- 如何保护自己的windows系统