2263 트리의 순회

두 트리의 순회가 주어졌을 때, 나머지 순회를 구하는 문제다

이 문제는 inorder와 postorder가 주어졌을 때, 나머지 순회인 postorder를 구하게 된다

 

이런 문제는 루트를 구하고, 루트를 기준으로 왼쪽과 오른쪽을 나눈 다음 재귀함수를 호출하면 구할 수 있게 된다

1. 루트는 postorder의 마지막 원소가 된다

2. inorder에서 루트값이 나오기 전까지가 왼쪽 자식이고, 루트 값 이후의 값이 오른쪽 자식이 된다

3. 이를 재귀함수를 돌리면 된다

 

vector로 하면 좋지만, 메모리를 계속 생성하면서 재귀 구조이기 때문에 메모리 초과가 일어난다

그래서 인덱스로 접근하는 것이 옳다

 

계속 헤맸던 부분이 인덱스를 올바르지 못하게 접근했던 것이다. 
포스트오더와 인오더의 공통점은 루트를 기준으로 왼쪽 트리의 '개수'가 같은 것이지, 인덱스 번호가 일치할지는 모르는 것이다. 따라서 포스트오더의 기준점에서 루트까지 몇번 움직였는지를 더해주어야만 구해질 수 있다

 

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

깃허브주소: https://github.com/surinoel/boj/blob/master/2263.cpp

 

 

[+추가] root 인덱스를 찾는데 시간이 많이 걸렸는데, 이 부분을 배열을 하나 만들어서 입력에서 미리 저장해놓으면 빨리 구할 수 있다. 약 100배 빨라진다