uva548
/* 1: 2: getline sstream , 3: getline sstream */
#include <iostream>
#include <cstdio>
#include <sstream>
#include <string>
using namespace std;
const int maxn = 10000 + 1;
int in_order[maxn], post_order[maxn], lchild[maxn], rchild[maxn]; //lchild[i] i
int n; //
int best, best_sum; //
bool read_input(int * a) {
string str;
if(!getline(cin, str)) return false; //getline stringstream
stringstream ss(str); n = 0;
int val;
while(ss >> val) a[n++] = val;
return n > 0;
}
int make_tree(int start1, int end1, int start2, int end2) {
if(start1 > end1) return 0;
int root = post_order[end2];
int p = start1;
while(in_order[p] != root) p++;
int lchild_num = p - start1; //
lchild[root] = make_tree(start1, p-1, start2, start2 + lchild_num - 1);
rchild[root] = make_tree(p+1, end1, start2 + lchild_num, end2-1); //
return root;
}
void dfs(int node, int sum) { // node , sum
sum += node; //
if(!lchild[node] && !rchild[node]) {
if((sum < best_sum) || (sum == best_sum && node < best)) { //
best_sum = sum;
best = node;
}
}
if(lchild[node]) dfs(lchild[node], sum);
if(rchild[node]) dfs(rchild[node], sum);
}
int main()
{
while(read_input(in_order)) {
read_input(post_order); //
make_tree(0, n-1, 0, n-1); //
best_sum = 100000;
dfs(post_order[n-1], 0); // , 0
printf("%d
", best);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
9. 데이터 구조의 이 진 트 리그 다음 에 우 리 는 이 진 트 리 의 생 성, 소각, 옮 겨 다 니 기, 그리고 각종 이 진 트 리 의 성질 에 착안 하여 (높이, 노드 개수, 균형 여부 등 특성) 이 진 트 리 의 일부 응용 을 소개 해 야 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.