[TIL] 211004 (트리순회, LCA)

• BOJ 2263_트리의 순회 를 풀면서 2가지 순회가 주어졌을때 (inorder는 무조건 주어져야 한다.) 나머지 순회를 재구성하는 방법을 공부했다.
  혼자서는 짜기가 어려워서 다른분의 풀이를 내 방식으로 재구성하여 정리 해봤다.
  아직은 어설프긴 한데, 몇번 응용해서 풀어보면 익숙해질 것 같다.
  (원본 출처)

import sys
sys.setrecursionlimit(10**6)
def inpostToPre(inL, inR, postL, postR):
    if inL > inR or postL > postR: return
    root = postOrder[postR]
    mid = pos[root]
    left,right = mid - inL,inR - mid
    print(root, end=" ")
    inpostToPre(inL, inL + left - 1, postL, postL + left - 1)
    inpostToPre(inR - right + 1, inR, postR - right, postR - 1)
    
N = int(input())
inOrder,postOrder=list(map(int,input().split())),list(map(int,input().split()))
pos = [0 for _ in range(N+1)]
for index,value in enumerate(inOrder): pos[value] = index
inpostToPre(0,N-1,0,N-1)

• 트리구조에서 자주 쓰이는 LCA 알고리즘을 공부했다.
  코드만 보면서 공부해보려고 노력했는데 쉽지않아서 유튜브 강의를 참고하면서 공부했다.
  강의는 우리학교 교수님인 신찬수 교수님 영상, 동빈나님 영상 을 참고했다.
  내일 관련내용을 포스팅 할 예정이다.