[LeetCode] 102. Binary Tree Level Order Traversal 풀이 및 코드

문제

트리를 level 순으로 순회하여 각 레벨 별 노드의 값을 리턴한다.

---

풀이

이 문제는 트리를 level 순으로 순회하는 문제이기 때문에 BFS(너비 우선 탐색)가 적합하다.

트리의 루트부터 leaf까지 순회를 하면서 한 레벨 씩 리스트에 담는다. 한 레벨 씩 리스트에 담기 위해서는 이전 레벨의 노드들의 리스트를 받아 해당 노들들의 left, right을 리스트에 넣으면 된다.

---

코드

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return root
        
        binary_tree_list, queue = [], [root]
        while len(queue) != 0:
            children, parent_val = [], []
            while len(queue) != 0:
                parent = queue.pop(0)
                parent_val.append(parent.val)
                if parent.left:
                    children.append(parent.left)
                if parent.right:
                    children.append(parent.right)
            queue = children
            binary_tree_list.append(parent_val)
        return binary_tree_list             

---

리트코드 제출 결과

LeetCode 제출 결과

---

참조

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