본문 바로가기
알고리즘 문제/Leetcode

[leetcode][116] Populating Next Right Pointers in Each Node

by 햄과함께 2020. 11. 15.
320x100

문제 : leetcode.com/problems/populating-next-right-pointers-in-each-node/


같은 depth를 가진 노드들을 왼쪽에서부터 오른쪽 형제들을 각 노드들의 next 포인터로 연결한다.


노드들을 왼 -> 오 순으로 연결하기 때문에 노드들을 탐색하면서 왼쪽 자식, 오른쪽 자식 순으로 탐색해나간다.

같은 depth를 가진 노드들을 연결하기 때문에 depth를 key 값으로 하고 해당 depth들 중 가장 마지막에 탐색된 노드 포인터를 value 값으로 하는 map을 만든다. 탐색하면서 탐색 중인 노드의 depth로 가장 마지막 노드 정보를 가져와서 가져온 노드의 next 포인터에 현재 탐색 중인 노드 포인터를 넣는다. 그리고 value 를 현재 탐색중인 노드로 갱신한다.

이를 루트 노드부터 탐색을 시작하면 된다.

 

시간복잡도는 노드 수를 N이라 할 때 O(N).


소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/116.%20Populating%20Next%20Right%20Pointers%20in%20Each%20Node.cpp

320x100

댓글