题意:给你中序后序 求某叶子节点使得从根到该节点权值和最小。若存在多个,输出其权值最小的那个。

题解:先建树,然后暴力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");
}

最新文章

  1. JavaScript 中的类方法,对象方法,Prototype方法
  2. PHP热身
  3. Linux之进程管理
  4. yii框架各种防止sql注入,xss攻击,csrf攻击
  5. Ubuntu中MySQL中文乱码解决
  6. 动态创建WebService
  7. Android Adapter的getViewTypeCount和getItemViewType
  8. Bootsrap 的 Carousel
  9. Oracle中Union与Union All的区别(适用多个数据库)
  10. 51nod 1451 合法三角形 判斜率去重,时间复杂度O(n^2)
  11. Oracle-05:伪表dual
  12. 给zTree的treeNode添加class
  13. (初)Knockout 监控属性(Observables)
  14. 利用websocket实现微信二维码码扫码支付
  15. WEX5中ajax跨域访问的几种方式
  16. SpringMVC 复杂对象数据绑定
  17. double转换为二进制
  18. [luogu1447][bzoj2005][NOI2010]能量采集
  19. 常用的cpl 命令 运行直接打开控制台的简单方法
  20. pgm8

热门文章

  1. 使用npm国内镜像
  2. tomcat 的 server.xml配置文件
  3. grid网格的流动grid-auto-flow属性
  4. MessageDigest类提供MD5或SHA等加密算法
  5. SpringBoot application.properties (application.yml)优先级从高到低
  6. urllib 基础模块
  7. [SublimeText] 如何创建工程
  8. codeforces水题100道 第二十一题 Codeforces Beta Round #65 (Div. 2) A. Way Too Long Words (strings)
  9. Objective-C官方文档 协议
  10. java高级----&gt;Thread之ExecutorService的使用