[Leetcode] 102. Binary Tree Level Order Traversal

문제 바로가기

BFS

Time Complexity: $O(n)$
Space Complexity: $O(n)$

from collections import deque

# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
        queue = deque()
        queue.append((root, 0))
        res, level = list(), list()
        curDepth = 0
        
        while queue:
            node, depth = queue.popleft()
            if curDepth != depth:
                res.append(level)
                level = list()
                curDepth = depth
            if node is None:
                continue
            level.append(node.val)
            queue.append((node.left, depth + 1))
            queue.append((node.right, depth + 1))
        
        return res

DFS

preorder 방식으로 DFS로 탐색하는 방식이다. queue를 사용하지 않으므로 더 적은 시간이 소모된다.

Time Complexity: $O(n)$
Space Complexity: $O(\log n)$ - res를 얻기 위해 필요한 추가 공간

from collections import deque

# 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 levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = list()
        def DFS(root: TreeNode, depth: int):
            if root is None:
                return
            if len(res) == depth:
                res.append([root.val])
            else:
                res[depth].append(root.val)
            DFS(root.left, depth + 1)
            DFS(root.right, depth + 1)
        
        DFS(root, 0)
        return res