0. 문제
https://leetcode.com/problems/populating-next-right-pointers-in-each-node/
1. 문제 설명
- 문제에서 완전 이진트리(root)가 주어진다.
- 모든 노드는 next 속성이 있는데, 이는 우측 노드를 가리키는 포인터 역할을 한다.
- 모든 노드의 next 값은 null 값으로 초기화되어있다.
- next 값이 우측에 존재하는 형제 노드를 가리키도록 설정하는 것이 문제의 핵심이다.
2. 문제 해설
a) 첫 번째 접근
- 우선 Level order 탐색을 이용한 방법을 생각할 수 있다.
- 어떤 노드를 방문할 때마다 해당 노드의 좌우에 존재하는 자식 노드를 Queue에 저장한다.
- 그리고 Queue에 저장된 노드를 순서대로 방문한다. 이 과정을 반복한다.
- 그러나 이 방식은 반복문을 이중으로 사용해야 하므로 효율적인 탐색이라고 할 수는 없다.
b) 두 번째 접근
- 더욱 효율적인 탐색을 위해 재귀 함수를 사용할 수 있다.
- 완전 이진트리는 좌측 자식 노드가 존재하는 경우, 우측 노드는 무조건 구조적 특징을 가진다.
- 이 특성을 이용하여 재귀적으로 탐색을 수행할 수 있다.
- 다음 코드를 보면서 이해해보자.
3. 정답 코드
a) Queue를 사용한 방법
class Solution {
public Node connect(Node root) {
if(root == null) return null;
Queue<Node> que = new LinkedList<>();
que.offer(root);
while(que.size() > 0) {
int count = que.size();
while(count > 0) {
count--;
Node node = que.poll();
if(count > 0) {node.next = que.peek();}
else if(count == 0) {node.next = null;}
if(node.left != null) {que.offer(node.left);}
if(node.right != null) {que.offer(node.right);}
}
}
return root;
}
}
b) 재귀를 사용한 방식
class Solution {
public Node connect(Node root) {
if(root == null) return null;
if(root.left != null) {
root.left.next = root.right;
}
if(root.right != null && root.next != null) {
root.right.next = root.next.left;
}
connect(root.left);
connect(root.right);
return root;
}
}
'Algorithm > 알고리즘 문제풀이' 카테고리의 다른 글
LeetCode 994(Rotting Orange, java) (0) | 2022.05.06 |
---|---|
LeetCode 542(01 Matrix, java) (2) | 2022.04.30 |
LeetCode 617(Merge Two Binary Trees, java) (0) | 2022.04.28 |
LeetCode 695(Max Area of Island, java) (0) | 2022.04.27 |
LeetCode 733(Flood Fill, java) (0) | 2022.04.27 |
댓글