[Leetcode 102] - Binary Tree Level Order Traversal w/ Python

 

 

Given the root of a binary tree, return the level order traversal of its nodes' values. 

(i.e., from left to right, level by level).

 

 

이진 트리가 주어졌을때 각 레벨 순서 순회의 값을 찾아서 리턴하는 문제

 

 

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

 

 

---

 

 

 

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

 

 

 

Example 2:

Input: root = [1]
Output: [[1]]

 

 

 

Example 3:

Input: root = []
Output: []

 

 

---

 

 

 

문제를 보고 바로 BFS를 통해 문제를 풀어야겠다 생각했다

 

1. que에 값이 있을때 현재 길이를 먼저 저장 (다음 레벨에 침범하지 않게)

2. 같은 레벨 노드를 처리하고 있을때 자식 노드들 que에 아주 몰래 append하기

3. 레벨의 끝에 도달했고 확인한 모든 노드가 None이 아닐때만 정답 리스트에 append

 

class Solution:
    def levelOrder(self, root):
        ans = []
        que = deque()
        que.append(root)

        while que:
            length = len(que)
            level = []

            for _ in range(length):
                curr = que.popleft()
                if curr:
                    level.append(curr.val)
                    que.append(curr.left)
                    que.append(curr.right)
            
            if level: 
                ans.append(level)
        
        return ans

 

 

나쁘지 않은 속도, 미친 메모리

 

 

 

---

 

 

 

근데 BFS로 풀어본 다음에 Dictionary를 사용해서 풀이를 하는게 더 낫지 않나...?라고 고민을 해봤다

 

 

 

1. Count를 통해 현재 레벨을 확인 가능

2. 딕셔너리에 [레벨 : {값들}] 추가

3. 자식 노드 (왼, 오)로 재귀

 

class Solution:
    def levelOrder(self, root):
        def traverse(self, root, count):
            if not root: return

            ans[count].append(root.val)
            traverse(self, root.left, count + 1)
            traverse(self, root.right, count + 1)
            
            return
        
        ans = defaultdict(list)
        traverse(self, root, 0)

        return ans.values()

 

 

압도적인 속도, 이모 메모리 부족해요