[백준,c++] 22856번 - 트리 순회

문제

22856번: 트리 순회

 

코드

#include <iostream>
#include <vector>
using namespace std;

vector<int> graph[100001];
bool visited[1000001];
int end_node;
int ans = 0;
bool flag = true;
void go(int node){

    int left_node = graph[node][0];     // 노드외 좌측 자식
    int right_node = graph[node][1];    // 노드의 우측 자식
    
    if(left_node != -1){
        ans+=1;
        go(left_node);
        if(flag) ans+=1;
    }
    if(right_node != -1){
        ans+=1;
        go(right_node);
        if(flag) ans+=1;
    }
    if(node == end_node){
        flag = false;
        return;
    }
}

void inorder(int node){
    int left_node = graph[node][0];
    int right_node = graph[node][1];
    
    if(left_node != -1){
        inorder(left_node);
    }
    end_node = node;
    if(right_node != -1){
        inorder(right_node);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N; cin>>N;
    for(int i=0; i<N; i++){
        int a, b, c; cin>>a>>b>>c;
        graph[a].push_back(b);
        graph[a].push_back(c);
    }
    inorder(1);  // 중위순회의 끝 노드를 찾음.
    go(1);   // 유사 중위순회 탐색
    cout<<ans;
}

 

풀이

 

트리

문제 예시 트리입니다. 트리의 중위 순회 순서는 Left -> Root -> Right 입니다. 트리의 순회 순서를 정리한 글은 아래에 있습니다.

이진트리 탐색 운행법

위 트리를 중위 순회하게 되면 4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7입니다. 이때 중위 순회의 끝은 7이며, 문제의 유사 중위 순회의 끝은 중위 순회의 끝 노드인 7이 되어야 합니다.

유사 중위순회

위 이미지는 문제에서 요구하는 유사 중위순회의 탐색 순서입니다.

루트인 노드 1에서 시작해서 중위순회의 끝 노드인 7에서 끝나며 1 -> 2 -> 4 -> 5 -> 2 -> 1 -> 3 -> 6 -> 3 -> 7과 같은 순서로 순회를 합니다.

따라서 문제 풀이 아이디어는 다음과 같습니다.

1. 중위 순회를 하여 중위 순회의 끝 노드를 찾는다.
2. 중위 순회를 시작하여 각 노드를 탐색할 때마다 방문 횟수를 + 1 추가하고, 왕복이기 때문에 탐색하고 나왔을 때도 방문 횟수를 +1 해준다.
3. 만약 방문 노드가 중위순회의 끝 노드라면, 왕복까지 하지 않고 해당 노드에서 끝나기 때문에 bool 변수를 따로 체크하여 방문 횟수를 한 번만 하고 종료하도록 한다.