마늘 계산객 난제 라이브러리 140 비귀속 두 갈래 나무의 뒷차례 두루 훑어보다
15.3%
1000ms
65536K
층수가 10보다 작은 두 갈래 트리를 지정하고 그 뒤에 흐르는 노드 이름 서열을 출력합니다.
입력은 한 줄을 포함하고 빈칸으로 구분된 각 노드는 두 갈래 나무의 층별 역행 순서에 따라 주어진다. 각 노드의 형식은 X(Y,num), X는 이 노드, Y는 부모 노드, num은 0, 1, 2 중의 하나, 0은 루트 노드, 1은 아버지 노드의 왼쪽 자절점, 2는 아버지 노드의 오른쪽 자절점을 나타낸다.한 줄로 출력하고 뒷줄로 훑어보는 결과입니다.
예제 1
입력:
A(0,0) B(A,1) C(A,2) D(B,1) E(B,2) F(C,1) G(D,1) H(D,2)
출력:
G H D E B F C A
#include<iostream>
#include<map>
#include<stack>
using namespace std;
struct btNode{
char c;
btNode *left, *right;
btNode(char ch) : c(ch), left(NULL), right(NULL){}
};
bool firstFlag;
/*
void postOrder(btNode *root){
if(root == NULL){
return;
}
postOrder(root->left);
postOrder(root->right);
if(firstFlag){
firstFlag = 0;
}else{
putchar(' ');
}
printf("%c", root->c);
}
*/
void postOrder(btNode * root){
btNode *cur, *pre = NULL;
stack<btNode*> sk;
sk.push(root);
while(!sk.empty()){
cur = sk.top();
if(cur->left == NULL && cur->right == NULL ||
pre != NULL && (pre == cur->left || pre == cur->right)){
sk.pop();
if(firstFlag){
firstFlag = 0;
}else{
putchar(' ');
}
putchar(cur->c);
}else{
if(cur->right){
sk.push(cur->right);
}
if(cur->left){
sk.push(cur->left);
}
}
pre = cur;
}
}
int main(){
// freopen("test.txt", "r", stdin);
char ch, fa, lr;
map<char, btNode*> mp;
btNode *root, *p, *q;
while(scanf("%c(%c,%c) ", &ch, &fa, &lr) == 3){
if(fa == '0'){
root = new btNode(ch);
mp[ch] = root;
}else{
p = mp[fa];
q = new btNode(ch);
mp[ch] = q;
if(lr == '1'){
p->left = q;
}else{
p->right = q;
}
}
}
firstFlag = 1;
postOrder(root);
cout << endl;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
9도 OJ 1116: 가감승제(기초문제)시간 제한: 1초 메모리 제한: 32메가바이트 특수 판제: 아니요 제출: 1466 해결 방법: 902 제목 설명: 입력한 연산자에 따라 입력한 정수에 대해 간단한 정수 연산을 진행한다.연산자는 더하기 +, 빼기 -,...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.