[분할정복]2250번 트리의 순회(C++)

https://www.acmicpc.net/problem/2263

뇌가 쫄깃해지는 문제

 

[TREE] 백준 1991번 트리의 순회(C++)

[TREE] 백준 1991번 트리의 순회(C++)

이 문제 보고오고

 

 

문제는 간단하다

inorder와 post 순서만보고

 

pre 오더 순서를 그려내라.

 

흠

너무 어려워

 

사실 이런건 아무거나 예시를 보면서 하는게 빠를거 같아서

 

구글에 나오는 예시 암거나 보면서 했다

 

9
1 3 4 5 6 7 12 15 16
1 4 6 5 3 12 16 15 7

 

입력을 이것이라 했을 떄

 

뭔가 보니까

 

    // 1 3(세미루트) 4 5 6 / 7 /12 15 16(맨 오른쪽) * 인오더 *

    // 1(맨 왼쪽) 4 6 5 3 / 12 16 15 7(루트) * 포스트오더 *

이렇게 봐바라..

 

우선

post order에서 맨 마지막에 있는것은, 기존 노드의 루트네?

어라 그리고 또 이제 그 루트노드의 순서를 가지고

inorder에서 왼쪽 오른쪽으로 나눠지네? ( 왼쪽은 왼쪽자식노드~~~,오른쪽은 오른쪽자식 노드~~~)

바로 이렇게

 

어 그럼 여기서

재귀를 사용할 수 있겠다!

라는 생각이 들었다

 

왜냐면 또 왼쪽노드에서

3이 루트노드가 되는데

 

postorder에서 보면

 // 1(맨 왼쪽) 4 6 5 3 / 12 16 15 7(루트) * 포스트오더 *

내가 왼쪽 오른쪽 기준으로 나눈 왼쪽 트리에서도

 

가장 오른쪽에 있는 3이 또 부모노드가 되네???

 

그렇다면 오른쪽으로 가면, 12 16 15에서 맨 오른쪽에있는 15가 또 부모노드가 되네?

 

이걸 계속~~ 반복하는것이 답에 접근하는 법임을 깨달았다.

 

그럼

1 3 4 5 6  7 12 15 16

1 4 6 5 3 12 16 15 7

를 가지고 규칙을 잘 찾아보자

 

1.먼저 포스트 오더에서 기준으로하는 트리의 맨 오른쪽 노드는 루트노드이다

2.그 루트 노드값으로 inorder의 루트노드의 위치를 찾는다

3.인덱스 기준 왼쪽 트리, 오른쪽 트리로 나눈다

4.왼쪽으로 가는경우, 트리의 인덱스 범위는 , 기존 트리의 인덱스 시작위치 -> 루트노드의 인덱스 이전까지 ( 여기서는 1부터 5 )

5.오른쪽으로 가는 경우, 트리의 인덱스 범위는 ,기존 트리의 루트노드 인덱스 -> 기존트리의 마지막 인덱스 -1 까지 간다

 

앞서 설명한 내용은

1~5 /6/7~9

 

이렇게 나뉘는 거고

1~5에서 반복

7~9에서 반복 하면 된다 

 

하지만 내가 여기까진 생각을 했는데

 

이후에 문제가 너무 안풀렷다 ㅠㅠ

 

사실 포스트 오더의 위치가 계속꼐속해서 밀리기 때문이였다

왼쪽 트리만 가는 경우, 인덱스의 위치는 변함이 없지만, 오른쪽으로 가는경우 기존 인오더의 위치에서 1 옆으로 밀리지않는가? 이게 문제였던것

 

이렇게 인덱스 위치가 바뀌는걸 신경써줘야 했던 것이였던것...

 

하 골드1인 이유가 있더라니

 

그냥 1차이만 생각했는데 이게 중첩되는거 같더라고

 

그래서 따로 postorder의 순서와 inorder의 순서를 고려해주면서 재귀함수를 완성하면 됨

 

예를들어

왼쪽으로 가는 경우

left = 1 , right = 5 | post _left = 1 (post_left), post_right= 5 (post_left+ 왼쪽_크기 -1)

 

왜 post_left + 크기 -1 인가.. 

 

그 이유는!!!

그 크기만큼 시작점에서 마지막점까지 계산을 위함

(root_index+1, right, post_left + left_size, post_right - 1);

오른쪽으로 가는 경우

 

이렇게 계속 post 와 inorder의 순서를 고려해주면서 만들면 되었던 것

 

나는 그냥 인오더 순서를 기준으로만 계속 했어가지고 헤맸음 ㅠ.

 

흠

잘모르겠음

아직도머리가아픔

 

#include <iostream>

#include <vector>

using namespace std;

vector<int> v[100001];

int arr_1[100001];

int arr_2[100001];

int n;

void result(int left, int right, int post_left, int post_right)

{

    if (left > right || post_left > post_right)

    {

        return;

    }

    int root = arr_2[post_right];

    cout << root << " ";

    int m_index = -1;

    for (int i = left; i <= right; i++)

    {

        if (arr_1[i] == root)

        {

            m_index = i;

            break;

        }

    }

    int left_size = m_index - left;

    if (m_index - 1 >= left)

    {

        int m_bef = m_index - 1;

        result(left, m_bef, post_left, post_left + left_size - 1);

    }

    if (m_index + 1 <= right)

    {

        int m_aft = m_index + 1;

        result(m_aft, right, post_left + left_size, post_right - 1);

    }

}

int main()

{

    int n;

    cin >> n;

    // 입력 인오더(왼쪽 중간 오른쪽)

    // 포스트오더(왼쪽 오른쪽 중간)

    // 출력 프리오더(중간 왼쪽 오른쪽)

    // 9개

    // 1 3(세미루트) 4 5 6 / 7 /12 15 16(맨 오른쪽) * 인오더 *

    // 1(맨 왼쪽) 4 6 5 3(세미루트) / 12 16 15 7(루트) * 포스트오더 *

    // 1 7 16

    for (int i = 1; i <= n; i++)

    {

        cin >> arr_1[i];

    }

    for (int i = 1; i <= n; i++)

    {

        cin >> arr_2[i];

    }

    result(1, n, 1, n);

}

나도 고수가되고싶어