Populating Next Right Pointers in Each Node
[문제]
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:
struct Node {
int val;
Node left;
Node right;
Node *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
[입력 조건]
The number of nodes in the tree is in the range [0, 212 - 1].
-1000 <= Node.val <= 1000
[추가 사항]
You may only use constant extra space.
The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.
[내 풀이]
class Solution:
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
if root is None:
return None
# 왼쪽 자식과 오른쪽 자식을 연결
if root.left is not None and root.right is not None:
root.left.next = root.right
# 오른쪽 자식을 다음 노드의 왼쪽 자식과 연결
if root.next is not None:
root.right.next = root.next.left
# 왼쪽 및 오른쪽 서브트리에 대해 재귀적으로 연결
self.connect(root.left)
self.connect(root.right)
return root해결 방법
🎯 문제 소개
완전 이진 트리가 주어지고, 각 노드의 next 포인터를 설정해서 그 노드의 다음 오른쪽 노드를 가리키게 해야 해요.(시각적으로) 만약 다음 오른쪽 노드가 없으면, next 포인터는 NULL로 설정해야 합니다.
🤔 접근 방법
각 노드의 왼쪽 자식을 오른쪽 자식과 연결
각 노드의 오른쪽 자식을 다음 형제 노드의 왼쪽 자식과 연결
이 작업을 재귀적으로 트리의 모든 레벨에 적용 (완전 이진 트리 조건)
💡 해결 과정
기저 사례 처리:
루트가 None인 경우, 그냥 None을 반환해요.
자식 연결:
현재 노드의 왼쪽 자식과 오른쪽 자식을 연결해요.
현재 노드에 next 포인터가 있으면(루트노드 or 오른쪽 노드가 아니면), 오른쪽 자식을 다음 형제 노드의 왼쪽 자식과 연결해요.
재귀적 호출:
왼쪽 및 오른쪽 자식에 대해 같은 작업을 재귀적으로 수행해요.
😊 배운 점
트리에 미디움 난이도라 겁먹었지만 생각보다 막(?) 어렵지는 않았어요.
재귀를 사용하면 간결하게 문제를 해결할 수 있어요.
[출처]
https://leetcode.com/problems/populating-next-right-pointers-in-each-node
