[leetcode][987] Vertical Order Traversal of a Binary Tree

문제 : leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/

---

이진 트리 노드의 루트 노드가 주어진다.

루트 노드는 (0, 0) (x,y) 위치를 가지고 왼쪽 자식 노드, 오른쪽 자식 노드로 갈수록 (x-1, y-1), (x+1, y-1) 위치 값을 가진다.

동일한 x 좌표 값을 가지는 노드들의 val 값의 배열을 x 좌표의 오름차순 정렬하여 구하라.

만일 동일한 x 좌표 값을 가진다면 y 좌표의 오름차순 정렬된 배열을 가진다.

y좌표도 동일하다면 노드의 val 값을 오름차순 정렬한다.

---

dfs로 풀 수 있다.

루트노드로부터 왼쪽, 오른쪽 자식으로 탐색하면서 (x-1, y-1), (x+1, y-1)로 좌표 값을 갱신시킨다.

x 좌표를 키값, (y좌표, node의 val) pair 배열을 value로 가지는 map을 만들어 저장한다.

모든 트리를 탐색하여 map에 저장하였으면 map을 key 값의 오름차순으로 탐색하며 value의 배열을 y좌표 기준 정렬. 동일한 경우 val 기준 정렬을 한뒤에 정답 배열에 추가한다.

 

시간복잡도는 노드 개수를 N이라 했을 때, key 값에 정렬된 map을 만들어야 하므로 O(NlogN).

value 배열을 정렬하는데 시간이 추가로 더 소요된다.

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/987.%20Vertical%20Order%20Traversal%20of%20a%20Binary%20Tree.cpp

---

hard 치고 알고리즘 생각하기가 어렵지 않았다. 구현이 어렵다고 생각해서 hard인건가..?