📍 문제 설명
이진 트리의 root가 주어지면, 노드 값의 지그재그 레벨 탐색을 반환합니다.
(즉, 왼쪽에서 오른쪽으로, 다음 레벨에서 오른쪽에서 왼쪽으로 탐색하고, 둘을 번갈아 가며 탐색합니다).
📍 예시
-
예시 1
-
Input
root = [3,9,20,null,null,15,7]
-
Output
[[3],[20,9],[15,7]]
-
-
예시 2
-
Input
root = [1]
-
Output
[[1]]
-
-
예시 3
-
Input
root = []
-
Output
[]
-
📍 풀이 point
🔓 Try1 🔓
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root :
return []
queue = deque([root])
depth = 1
result = []
while queue:
level_size = len(queue)
level_value = []
for i in range(level_size):
node = queue.popleft()
level_value.append(node.val)
if depth % 2 == 1:
if node.right:
queue.append(node.right)
if node.left:
queue.append(node.left)
else:
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level_value)
depth +=1
return result
처음에 문제를 너무 단순하게 생각해서,
짝수 층 노드를 큐에 넣어줄 때는 왼-오 순서가 아닌 오-왼 순서로 넣어주고, 홀수 층 노드를 큐에 넣어줄 때는 왼-오 순서로 넣어주면 된다고 생각했다.
하지만 위 코드는 아래와 같은 테스트 케이스를 통과하지 못한다.
여기서 어떤 방향으로 코드를 수정해야할지 잘 떠오르지 않아 아예 다른 방법을 사용해서 풀어보았다.
🔓 Try2 🔓
최종적으로 노드의 value 리스트를 반환하면 되는 것이기에, 한 레벨에서의 값을 level_value 배열에 넣어주고 짝수 층일 때 배열 순서를 reverse 함수를 써서 뒤집어주는 것으로 방법 변경하였다.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root :
return []
queue = deque([root])
depth = 1
result = []
while queue:
level_size = len(queue)
level_value = []
for i in range(level_size):
node = queue.popleft()
level_value.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if depth % 2 == 0 :
level_value.reverse()
result.append(level_value)
depth +=1
return result
정리해서 설명하자면,
-
각 레벨에서의 노드 값을 왼-오 순서로
level_value리스트에 담아준다
(level_value는 레벨 값이 바뀌면 초기화). -
짝수 층일 경우
level_value에 담긴 값을reverse()를 사용하여 뒤집어준다. -
홀수 층일 경우는
level_value에 담긴 값을 그대로 둔다. -
각 레벨을 탐색한 후에는
result배열에level_value에 담긴 값을 append 해준다.
💡append 관련하여 새로 알게된 점💡
-
append는 리스트에 값을 추가할 때 사용되는데, 추가되는 값은 참조 형태로 리스트에 저장된다.
(즉, 리스트의 항목으로 객체의 참조를 추가하는 방식이다.)append하면 리스트에 단순히 값이 추가되는 형태인줄 알고 있었음..! -
예시
list_a = [1, 2, 3] list_b = [4, 5, 6] # list_a에 list_b를 추가 list_a.append(list_b) print(list_a) # 출력: [1, 2, 3, [4, 5, 6]]- 참조가 추가된다는 것은
list_b가 독립적으로 존재하며list_a의 마지막 요소는list_b를 참조하고 있다는 의미이다.
list_b.append(7) # list_b에 새로운 값을 추가 print(list_a) # 출력: [1, 2, 3, [4, 5, 6, 7]]list_a의 마지막 요소는list_b의 참조를 담고 있기 때문에list_b가 변경되면,list_a내의 해당 참조도 변경된 값을 반영하게 된다.
- 참조가 추가된다는 것은
