LeetCode 풀기 - 102. Binary Tree Level Order Traversal

102. Binary Tree Level Order Traversal

https://leetcode.com/problems/binary-tree-level-order-traversal/

Binary Tree Level Order Traversal - LeetCode

문제)

솔루션1) - 재귀적 방법

이진 트리 순회 문제입니다. 

Level Order Traversal 방식으로 접근해서 문제를 풉니다.

# 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: Optional[TreeNode]) -> List[List[int]]:
        # recursive solution
        d = {}
        
        def recursive(node, level):
            if node is None:
                return
            
            d.setdefault(level, []).append(node.val)
            
            # 자식 순회
            recursive(node.left, level+1)
            recursive(node.right, level+1)
            
        
        recursive(root, level=0)
        return list(d.values())

솔루션2) - 큐 자료구조

큐 자료구조를 사용합니다.

# 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: Optional[TreeNode]) -> List[List[int]]:
        q = deque()
        q.append(root)
        
        d = {}
        level = 0
        while q:
            for _ in range(len(q)):
                node = q.popleft()
                if node:
                    d.setdefault(level, []).append(node.val)
                    q.append(node.left)
                    q.append(node.right)
            
            level += 1
            
        return list(d.values())

 

 

함께보면 좋은 글:

https://wellsw.tistory.com/106

이진 트리 레벨 순회 (Binary Tree Level Order Traversal)

https://leetcode.com/problems/binary-tree-level-order-traversal/

Binary Tree Level Order Traversal - LeetCode