例题6-8 树（Tree，UVa 548)

本文主要是介绍例题6-8 树（Tree，UVa 548)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-548
分类：树
备注：DFS
分析：理解二叉树的中序遍历和后序遍历即可

代码如下：

#include<cstdio>
#include<string>
#include<sstream>
#include<iostream>
using namespace std;
const int maxn = 10000 + 5;
const int inf = 0x3f3f3f3f;
int InOrder[maxn], PostOrder[maxn], sum, ans;
int read(int* a)
{int cnt = 0, x;string s;getline(cin, s);stringstream ss(s);while (ss >> x)a[cnt++] = x;return cnt;
}
void dfs(int* in, int L1, int R1, int* post, int L2, int R2, int temp)
{if (L1 > R1 || L2 > R2)return;//越界temp += PostOrder[R2];if (temp > sum)return;//减少不必要的搜索,避免超时if (L1 == R1){if (temp < sum) { sum = temp; ans = InOrder[L1]; }else if (temp == sum) { ans = ans < InOrder[L1] ? ans : InOrder[L1]; }return;}int pos;//找根的位置for (pos = L1; pos <= R1; pos++)if (InOrder[pos] == PostOrder[R2])break;dfs(in, L1, pos - 1, post, L2, L2 + pos - L1 - 1, temp);dfs(in, pos + 1, R1, post, L2 + pos - L1, R2 - 1, temp);
}
int main(void)
{while (int len = read(InOrder)){read(PostOrder);sum = inf;dfs(InOrder, 0, len - 1, PostOrder, 0, len - 1, 0);printf("%d\n", ans);}return 0;
}

这篇关于例题6-8 树（Tree，UVa 548)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---