Question1 - [미들러] 홀수 층의 이진트리를 역배열 ( Reverse Odd Levels of Binary Tree)
문제설명 https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/description/
Given the root of a perfect binary tree, reverse the node values at each odd level of the tree.
For example, suppose the node values at level 3 are [2,1,3,4,7,11,29,18], then it should become [18,29,11,7,4,3,1,2].
Return the root of the reversed tree.
A binary tree is perfect if all parent nodes have two children and all leaves are on the same level.
The level of a node is the number of edges along the path between it and the root node.
Example 1:
Input: root = [2,3,5,8,13,21,34]
Output: [2,5,3,8,13,21,34]
Explanation:
The tree has only one odd level.
The nodes at level 1 are 3, 5 respectively, which are reversed and become 5, 3.
Example 2:
Input: root = [7,13,11]
Output: [7,11,13]
Explanation:
The nodes at level 1 are 13, 11, which are reversed and become 11, 13.
Example 3:
Input: root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
Output: [0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]
Explanation:
The odd levels have non-zero values.
The nodes at level 1 were 1, 2, and are 2, 1 after the reversal.
The nodes at level 3 were 1, 1, 1, 1, 2, 2, 2, 2, and are 2, 2, 2, 2, 1, 1, 1, 1 after the reversal.
Constraints:
- The number of nodes in the tree is in the range [1, 214].
- 0 <= Node.val <= 105
- root is a perfect binary tree.
문제풀이
간단한 문제인 것 같은데도....
우선 이 문제 설며을 보면, input의 루트 이동순서를 보니 BFS로 풀어야 한다.
너비 우선 탐색으로 root노드부터 같은 Level의 모든 노드를 탐색하고, 그 다음 Level로 내려가서 탐색해가며 작업을 수행해야 한다.
필요한 작업은, 홀수 Level에 대해서만 노드의 값들을 역순으로 재배열 하는 것.
BFS이니까 deque를 활용해서 탐색이 필요하다. 작업의 순서는 아래와 같다.
그리고 각 작업 및 기능은 독립된 메소드로 구현 한다.
1. 트리 객체 생성 :
TreeNode 클래스를 만들어 트리를 생성 한다.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
2. 리스트 (input_list) 를 트리로 변환 :
listToTreeNode 메소드를 만들어,
입력 리스트(input_list)를 이진 트리로 변환한다.
BFS(Breadth-First Search) 방식을 사용하여 큐(deque)를 활용하여 레벨 순서대로 노드를 생성하고 연결한다.
def listToTreeNode(self,lst):
if not lst :
return None
root = TreeNode(lst[0])
queue = deque([root])
index = 1
while queue and index < len(lst):
node = queue.popleft()
if index < len(lst) and lst[index] is not None :
node.left = TreeNode(lst[index])
queue.append(node.left)
index += 1
if index < len(lst) and lst[index] is not None :
node.left = TreeNode(lst[index])
queue.append(node.left)
index += 1
if index < len(lst) and lst[index] is not None :
node.right = TreeNode(lst[index])
queue.append(node.right)
index += 1
return root
3. 홀수번째 level의 노드 값들을 역순으로 배열 :
reverseOddLevels 메소드를 만들어,
이진 트리를 탐색하면서 홀수번째 레벨에 있는 노드들의 값을 역순으로 배열한다.
BFS를 사용하여 각 레벨의 노드들을 큐에 저장하고, 홀수번째 레벨일 때 노드 값을 역순으로 배열한다.
def reverseOddLevels(self, root):
if not root:
return None
queue = deque([root])
level = 0
while queue :
level_length = len(queue)
current_level = []
for _ in range(level_length):
node = queue.popleft()
current_level.append(node)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if level % 2 == 1 :
i, j = 0, len(current_level) -1
while i < j :
current_level[i].val, current_level[j].val = current_level[j].val, current_level[i].val
i += 1
j -= 1
level += 1
return root
4. 재배열된 트리를 리스트로 변환 및 반환 :
treeNodeToList 메소드를 만들어 변경된 이진 트리를 다시 리스트로 변환하여 반환한다.
BFS 방식을 사용하여 트리를 순회하고, 각 노드의 값을 리스트에 추가한다.
def treeNodeToList(self, root):
if not root :
return []
result = []
queue = deque([root])
while queue :
node = queue.popleft()
if node :
result.append(node.val)
queue.append(node.left)
queue.append(node.right)
else :
result.append(None)
while result and result[-1] is None :
result.pop()
return result
아래는 완성된 코드이다.
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def reverseOddLevels(self, root):
if not root:
return None
# 레벨 순서를 위한 큐
queue = deque([root])
level = 0
while queue:
level_length = len(queue)
current_level = []
# 현재 레벨의 노드들을 큐에서 꺼내어 저장
for _ in range(level_length):
node = queue.popleft()
current_level.append(node)
# 자식 노드들을 큐에 추가
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# 홀수 레벨의 노드 값을 반대로 뒤집기
if level % 2 == 1:
i, j = 0, len(current_level) - 1
while i < j:
current_level[i].val, current_level[j].val = current_level[j].val, current_level[i].val
i += 1
j -= 1
level += 1
return root
def listToTreeNode(self, lst):
if not lst:
return None
root = TreeNode(lst[0])
queue = deque([root])
index = 1
while queue and index < len(lst):
node = queue.popleft()
if index < len(lst) and lst[index] is not None:
node.left = TreeNode(lst[index])
queue.append(node.left)
index += 1
if index < len(lst) and lst[index] is not None:
node.right = TreeNode(lst[index])
queue.append(node.right)
index += 1
return root
def treeNodeToList(self, root):
if not root:
return []
result = []
queue = deque([root])
while queue:
node = queue.popleft()
if node:
result.append(node.val)
queue.append(node.left)
queue.append(node.right)
else:
result.append(None)
# 마지막 None 제거
while result and result[-1] is None:
result.pop()
return result
# 예제 출력
input_list = [2, 3, 5, 8, 13, 21, 34]
sol = Solution()
root = sol.listToTreeNode(input_list)
root = sol.reverseOddLevels(root)
output_list = sol.treeNodeToList(root)
print(output_list) # [2, 5, 3, 8, 13, 21, 34]'Dev' 카테고리의 다른 글
| [코테] 99클럽 코테 스터디 17일차 TIL - Greedy (0) | 2024.06.05 |
|---|---|
| [코테] 99클럽 코테 스터디 16일차 TIL - Greedy (0) | 2024.06.05 |
| [코테] 99클럽 코테 스터디 12일차 TIL - BFS (feat.최단경로) (0) | 2024.06.01 |
| [코테] 99클럽 코테 스터디 10일차 TIL - 완전탐색 (0) | 2024.05.30 |
| [코테] 99클럽 코테 스터디 9일차 TIL - 완전탐색 (0) | 2024.05.29 |