백준22856 - 트리순회

문제링크 : https://www.acmicpc.net/problem/22856
알고리즘 종류 : 트리, 구현
솔? : 답지 보고함
핵심 아이디어 : 기존 중위 순회에서 2배에서 루트 우측 트리의 우측 노드 방문 횟수를 빼누면 된다는 아이디어가 필요하다. 근데 map STL로 트리를 다루는 거도 쉽지 않다..

• 중위 순회를 구현한다.
• 계산된 (중위순회 방문횟수)x2 - (우측트리 우특 노드 방문 횟수)

#include <bits/stdc++.h>
using namespace std;

int N, Data, Left, Right;
//최초 노드 카운트는 제외해야하기 때문에 -1로 설정
int cnt = -1, Rcnt = -1;

map<int, pair<int, int>> tree;

void input() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d %d %d", &Data, &Left, &Right);
        //Data가 중복되면 알아서 좌우로 들어간다.
        tree[Data].first = Left;
        tree[Data].second = Right;
    }
}
//flag : 루트노드 기준 좌측 트리 우측트리 구분자
void travel(int node, bool flag) {
    //해당노드가 없는 노드라면 함수 리턴
    if (node == -1) return;
    //순회 횟수 증가
    cnt++;
    //좌측 노드 순회
    travel(tree[node].first, 0);
    //우측 노드에 도달했다면 우순회 횟수 증가
    if (flag) {
        //우측트리 우측 노드 방문 횟수 카운트
        Rcnt++;
        travel(tree[node].second, 1);
    }
    else {
        travel(tree[node].second, 0);
    }
}

int main() {
    input();
    travel(1, 1);
    printf("%d", 2 * cnt - Rcnt);
}

후기 : 중위순회부터 짜는 연습을 해야한다니..

잘설명된 링크 : https://comdolidol-i.tistory.com/280