Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
31 |
Tags
- 이진트리
- binary search
- HashTable
- binary tree
- sorting
- tree
- two pointers
- matrix
- Binary
- 중간
- Array
- hash table
- DP
- list
- string
- 리트코드
- recursive
- dfs
- 재귀
- 문자열
- math
- leetcode
- Python
- Depth-first Search
- easy
- linked list
- 쉬움
- backtracking
- 미디움
- Medium
Archives
- Today
- Total
부부의 코딩 성장 일기
LeetCode 103(Binary Tree Zigzag Level Order Traversal, Python) 본문
Algorithm/LeetCode
LeetCode 103(Binary Tree Zigzag Level Order Traversal, Python)
펩시_콜라 2024. 2. 22. 19:001. 문제 링크
LeetCode - The World's Leading Online Programming Learning Platform
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
2. 문제 설명
- binary tree의 root가 주어졌을 때, level 별로 zigzag 순서로 nodes의 값을 적재하여 반환
- level 0에서 왼쪽 → 오른쪽으로 path를 적재했다면,
- level 1에서는 오른쪽 → 왼쪽으로 path를 적재하는 것
- 예를 들어 아래와 같은 tree가 있다고 할 때,
- root node가 있는 level에서는 3을 적재하고, 그 다음 level에서는 [20, 9]의 순서로
- 그 다음 level에서는 반대로 [15,7]의 순서로 적재한다.
- 결국 Input root = [3,9,20,null,null,15,7]이면, output = [[3],[20,9],[15,7]]이 된다.
3. 처음 풀이
- 처음에 조금은 비효율적으로 접근했다.
- 우선 root, root.left, root.right를 path에 적재하는데,
- root에서 root.left, root.right로 갈 때 level이 한 개 증가하므로,
- root와 level을 인자로 받는 helper함수를 만들어서,
- 우선은 모든 level이 왼→오의 방향으로 쌓이게 만든 뒤에
- 나중에 for 문을 돌면서 홀수 층의 경우, list를 거꾸로 바꿔서 append했다.
- 해당 풀이가 비효율적인 이유는
- 한번 list에 쌓을 때 순서를 뒤집어가면서 하면 되는데, 굳이 다 만든 뒤에 뒤집기 때문.
# 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]]:
path = {}
def helper(root, level):
if root is None:
return
if level not in path:
path[level] = [root.val]
else:
path[level] += [root.val]
helper(root.left,level+1)
helper(root.right,level+1)
helper(root,0)
output = []
for index, i in enumerate(path.values()):
if index % 2 == 1:
output.append(i[::-1])
else:
output.append(i)
return output
4. 다른 풀이
- 많은 풀이에서 deque를 사용했다.
- 이걸 사용하지 않고, 앞에 원소를 쌓거나, 그냥 append하거나 둘 중 하나로 해도 되긴 하는데, 시간 복잡도에서 이점이 있다고 한다.
- deque는 collections 모듈(이건 leetcode에서 기본적으로 제공해준다.)의 함수이고 deque를 사용하면 리스트의 맨 앞에 원소를 추가하거나 제거할 때 O(1)의 시간복잡도를 가지므로 성능이 향상될 수 있다.
- 추가로 나는 내가 익숙한 DFS 방식으로 했는데, BFS로 너비 우선탐색을 해야 레벨 순서를 쉽게 처리할 수 있다.
- 아래의 코드를 보면
- 우선 root를 deque에 넣는 queue를 만들고,
- queue의 length만큼 for문을 돌리는데,
- queue에서 가장 왼쪽에 있는 node를 가져와서 해당 value를 append하고,
- 만약 node.left가 존재하면, queue에 node.left를,
- 만약 node.right가 존재한다면, queue에 node.right를 append한다.
- 그다음 지그재그 순서를 가야 하므로,
- 만약 reverse = True이면, result에 level_values를 거꾸로 뒤집어서 append하고,
- reverse = False이면, 그대로 append한다음에
- result를 반환
- 우선 root를 deque에 넣는 queue를 만들고,
# 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 []
result = []
queue = deque([root])
reverse = False
while queue:
level_values = []
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
level_values.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if reverse:
result.append(level_values[::-1])
else:
result.append(level_values)
reverse = not reverse
return result
- 위 풀이도 정리하다보니, 결국 또 [::-1]로 뒤집는게 나오는데 아래 코드처럼,
- left, right인지에 따라, append(node.val)을 하거나, insert(0,node_val)을 해서 가장 왼쪽에 삽입을 하면 바로 list에 추가 가능하다.
# 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]]:
res = []
queue = deque([root])
left_order = True
while queue:
level_res = []
for _ in range(len(queue)):
node = queue.popleft()
if node:
if left_order:
level_res.append(node.val)
else:
level_res.insert(0, node.val)
queue.append(node.left)
queue.append(node.right)
left_order = not left_order
if level_res:
res.append(level_res)
return res
5. 배운 점
- BFS 방식에 익숙해지기
'Algorithm > LeetCode' 카테고리의 다른 글
LeetCode 105(Construct Binary Tree from Preorder and Inorder Traversal, Python) (1) | 2024.02.24 |
---|---|
LeetCode 263(Ugly Number, Python) (0) | 2024.02.23 |
LeetCode 102(Binary Tree Level Order Traversal, Python) (0) | 2024.02.21 |
LeetCode 258(Add Digits, Python) (0) | 2024.02.20 |
LeetCode 98(Validate Binary Search Tree, Python) (0) | 2024.02.19 |