[백준 1539] 이진 검색 트리

이 문제때문에 짜증이 나지는 않았다.

시간초과가 계속 나는데 (사실 날 수 밖에 없었다. 날거라는 것도 안상태에서 반포기 반기대상태로 품)

정답을 보니 이건 틀릴만 했다. 아니 틀려야만 한다

왜? 내가 난생 처음보는 접근법이었기 때문.

무슨 알고리즘 이름이 있는것도 아니다.

그냥 새로운 접근법인데 알아놓으면 좋을듯

 

---

일단 이진검색트리는 아래와 같이 만들어진다.

이진검색트리는 완전이진트리가 아니다. 그냥 이진트리이다. 무조건 완전일 필요가 없다

근데 이 트리를 list 즉 vector로 표현할 수 있다

옆으로 늘리고 튀어나온 것들을 눌러줘서 말이다

즉 트리를 정렬된 리스트로 표현할 수 있다는거임

이건 이진검색트리를 전위순회하면 오름차순으로 나오는 걸 생각해보면 이해가 된다

 

그래서 이렇게 트리를 리스트로 표현하는 접근법을 알았으면

아래와 같이 lower_bound를 사용해서 노드가 들어갈 위치를 찾을 수 있다

그럼 이걸로 높이는 어떻게 계산하느냐

3번 노드가 들어갈 자리(lower_bound)와 그 이전 노드 높이 중 최대값을 골라 +1을 하면 3번 노드의 높이가 됨

 

만약 lower_bound가 없거나(root노드), lower_bound의 이전 값이 없으면 0으로 잡고 하면 된다