【紫书】Tree UVA - 548 静态建树dfs
2024-10-21 13:21:40
题意:给你中序后序 求某叶子节点使得从根到该节点权值和最小。若存在多个,输出其权值最小的那个。
题解:先建树,然后暴力dfs/bfs所有路径,取min
技巧:递归传参数,l1,r1,l2,r2, sum,root,
代码:
#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"
#include<stdio.h>
#include<algorithm>
#include<string>
#include<vector>
#include<list>
#include<set>
#include<iostream>
#include<string.h>
#include<queue>
#include<string>
#include<sstream>
using namespace std;
const int maxn = 1e4+;
string line; int n;
int a[maxn],in_order[maxn],post_order[maxn];
int lch[maxn], rch[maxn];
int mn,best;
bool read_list(int *a) {
if (!getline(cin, line)) return false;
stringstream ss(line);
n = ;
int x;
while (ss >> x)a[n++] = x;
return n > ;
}
int build(int l1, int r1, int l2, int r2) {//将中序l1,r1 将后序l2,r2 建成一棵树,返回树根
if (l1 > r1)return ;
int root = post_order[r2];
int p = l1;
while (in_order[p] != root)p++;
int cnt = p - l1;
lch[root] = build(l1, p - , l2, l2 + cnt - );
rch[root] = build(p + , r1, l2 + cnt, r2 - );
return root;
}
void dfs(int u, int sum) {
sum += u;
if (!lch[u] && !rch[u]) if (sum < mn || (sum == mn&&u < best)) {best = u; mn = sum;}
if (lch[u])dfs(lch[u], sum);
if (rch[u])dfs(rch[u], sum);
}
int main() {
while (read_list(in_order)) {
read_list(post_order);
build(, n - , , n - );
mn = 1e9;
dfs(post_order[n - ], );
cout << best << "\n";
} //system("pause");
}
最新文章
- JavaScript 中的类方法,对象方法,Prototype方法
- PHP热身
- Linux之进程管理
- yii框架各种防止sql注入,xss攻击,csrf攻击
- Ubuntu中MySQL中文乱码解决
- 动态创建WebService
- Android Adapter的getViewTypeCount和getItemViewType
- Bootsrap 的 Carousel
- Oracle中Union与Union All的区别(适用多个数据库)
- 51nod 1451 合法三角形 判斜率去重,时间复杂度O(n^2)
- Oracle-05:伪表dual
- 给zTree的treeNode添加class
- (初)Knockout 监控属性(Observables)
- 利用websocket实现微信二维码码扫码支付
- WEX5中ajax跨域访问的几种方式
- SpringMVC 复杂对象数据绑定
- double转换为二进制
- [luogu1447][bzoj2005][NOI2010]能量采集
- 常用的cpl 命令 运行直接打开控制台的简单方法
- pgm8
热门文章
- 使用npm国内镜像
- tomcat 的 server.xml配置文件
- grid网格的流动grid-auto-flow属性
- MessageDigest类提供MD5或SHA等加密算法
- SpringBoot application.properties (application.yml)优先级从高到低
- urllib 基础模块
- [SublimeText] 如何创建工程
- codeforces水题100道 第二十一题 Codeforces Beta Round #65 (Div. 2) A. Way Too Long Words (strings)
- Objective-C官方文档 协议
- java高级---->;Thread之ExecutorService的使用