LeetCode Populating Next Right Pointers in Each Node II

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

보통 Tree 는 root 밑에 left와 right 가 있다. 포인터는 이 두개만 있는 것이 보통의 트리인데, 이 문제에서는 left와 right 를 root 를 통하지 않고 바로 next 로 연결하기를 원한다. root의 root 를 통해야 하는 right 에서 left로의 연결도 해야한다. Balanced Binary Tree 라면 쉽게 풀 수 있다. 또 그런 문제도 있었다. 이번문제는 unBalanced Binary Tree 이다.
Balanced 의 경우에는 root의 left의 left의 left 는 null이 나올 때 까지 계속 존재하고, 맨 왼쪽에 있는 TreeNode 에서 left 에서 right 로 직접이동할 수 있는 next 포인터를 추가해줬고, right의 오른쪽에 있는 left TreeNode 에 연결하기 위해서는 root 의 next 를 타고 넘어가 연결을 해줬다.

하지만, 이 문제는 맨 왼쪽의 TreeNode 가 없을 수도 있다. 보통의 방식으로 했다간, NullPointerException이 나올 수 있다. 어제 풀었던 Level-Order Traversal을 응용하기로 했다.
위에서 아래로 level 에 따라서 queue 에 들어가게 되고, 각 level 은 왼쪽에서 오른쪽으로 들어가게 된다. queue 에서 뽑아가면서 next pointer 를 만들어 주면 아무리 TreeNode 가 멀리 떨어져 있어도 포인터를 구축 할 수 있다. iteration으로 가장 가까운 형제노드를 찾는 것은 너무 어렵다.