[Java] 트리 (이진 검색 트리)

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

5639번: 이진 검색 트리

 

오늘 취업전선에 먼저 뛰어든 여자동기 친구와 이런저런 스몰토크를 하다가 친구가 친 대기업에서 자료구조를 기반으로 한 코테 문제가 많이 나왔다는 소리를 듣고, 작년에 배운 자료구조를 생각해 보다가 트리에 대해 잘 기억이 안 나는 것 같아서 관련 문제를 풀어봤다.

 

자료구조 강의 시간에 C를 기반으로 배웠었는데 자바로 푸니까 확실히 선녀다. C로 할때는 트리 구성할 때 포인터로 연결하면서 되게 복잡했는데 자바는 포인터도 없고 클래스로 만드니까 좀 쉽네요~

 

내 기억에 전위 순회랑 중위 순회 둘다 있어야 후위 순회를 작성할 수 있었던 거 같아서 문제가 잘못됐나 했었는데! 당연히 그럴리는 없고 문제 조건이 이진 검색 트리라서 전위 순회 하나만 있어도 풀 수 있다.

 

전위 순회 하면 맨 먼저 루트 노드가 나오기 때문에 바로 루트 노드를 구성하고 그 뒤부터는 크기 비교해서 왼쪽 오른쪽 잘 달면 완성된다.