UVA 548 树 递归典型
程序员文章站
2022-03-13 20:48:23
...
题目大意(翻译):
给定一颗节点带权的二叉树的中序遍历序列和后序遍历序列,要求找出叶子节点中到根的路径上的权和最小的节点。
注:
1. 所有节点的权值都不同
2. 如果权和最小的叶子节点有多个,输出其中权值最小的。
题目思路:
- 首先根据后序遍历序列和中序遍历序列构建该二叉树。
- 从根节点进行DFS遍历整棵树,找到符合条件的叶子节点。
代码如下:
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
const int maxn = 10000+10;
int in_order[maxn],post_order[maxn],lch[maxn],rch[maxn]; // 使用两个数组构建二叉树
int n,best,best_sum;
bool read_list(int *a)
{
string s;
if(!getline(cin,s)) return false;
stringstream ss(s);
n = 0;
int x;
while(ss>>x) a[n++] = x;
return n > 0; // 作用是当遇到空行时,直接返回。
}
int build(int L1,int R1,int L2,int R2)
{
if(L1>R1) return 0;
int root = post_order[R2];
int p = L1;
while(in_order[p]!=root) p++;
int cnt = p-L1;
lch[root] = build(L1,p-1,L2,L2+cnt-1);
rch[root] = build(p+1,R1,L2+cnt,R2-1);
return root;
}
void dfs(int v,int sum)
{
sum += v;
if(!lch[v] && !rch[v]) { // 叶子节点
if(sum < best_sum || (sum==best_sum && v < best)) {
best = v; best_sum = sum;
}
}
if(lch[v]) dfs(lch[v],sum);
if(rch[v]) dfs(rch[v],sum);
}
int main()
{
while(read_list(in_order)) {
read_list(post_order);
build(0,n-1,0,n-1);
best_sum = 1 << 30;
dfs(post_order[n-1],0);
cout << best << endl;
}
return 0;
}
上一篇: TextView 实现打电话功能
下一篇: 专科男生最吃香的专业-专科热门专业男生
推荐阅读
-
Tree UVA - 548 (DFS+建立二叉树)
-
Uva548(二叉树通过中序和后序遍历数据创建树)
-
【代码超详解】UVA 548 Tree 树(二叉树、DFS)
-
二叉树遍历(前序、中序、后序) UVA 548 Tree
-
数据结构-树与二叉树-二叉树的递归遍历(Tree UVA - 548||Not so Mobile UVA - 839||The Falling Leaves UVA - 699)
-
UVA 548 根据中序和后序建立二叉树并求根到叶的最短路
-
uva 806(四叉树dfs 递归 )
-
UVA 548 - Tree(树)
-
例题6-6 UVa679-Dropping Balls(满二叉树、递归)
-
UVA 548 树 递归典型