LeetCode 107(Binary Tree Level Order Traversal II, Python)

1. 문제 링크

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

LeetCode - The World's Leading Online Programming Learning Platform

 

2. 문제 설명

• 이진트리의 root가 주어졌을 때, bottom-up level order traversal을 반환
  • 여기서 bottom-up leverl order란 가장 bottom순서부터 node의 왼쪽부터 오른쪽까지 list에 쌓아서 반환
• 예시) 아래와 같은 tree가 주어졌다면, (input root = [3,9,20,null,null,15,7]
  • 가장 아래 level의 node 부터 list로 쌓아나간다.
  • output = [[15,7], [9,20],[3]]

 

3. 처음 풀이 

• 해당 문제는 기존 Binary Tree Level Order Traversal I의 결과값을 거꾸로 reverse한 것과 같아서,
• 우선 기존 풀이처럼 root node부터 쌓고, return할 때 [::-1]를 통해 결과값을 거꾸로 뒤집었다. (분명 더 좋은 풀이가 있을 거라 생각하면서 우선은..) 기존에 풀었던 풀이는 아래와 같다.
  • 먼저 root와 level을 인자로 받는 helper 함수를 만들어두고, level_hist 라는 빈 dictionary에 level 마다 node값을 append하는 방식으로 작성하였다.
    • root.val을 level_hist[level]에 추가하고, 
    • root.left과 root.right는 level이 한 층 더해지는 것이므로, helper(root.left, level+1)와 helper(root.right, level+1)를 호출하고, 
    • 최종적으로 list(level_hist.values())를 반환했다.
  • 그래서 이번 문제에서는 list(level_hist.values())[::-1]를 하니, runtime이 80%정도로 통과하였다. 

# 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 levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        level_hist = {}
        def helper(root,level): 
            if root is None:
                return 
            
            if level in level_hist:            
                level_hist[level] += [root.val] 
            else:
                level_hist[level] = [root.val]
        
            helper(root.left, level+1)
            helper(root.right, level+1)
        
        helper(root,0)
        
        return list(level_hist.values())[::-1]

4. 다른 풀이

• 뭔가 기존 풀이의 순서를 뒤집기만 해서 반환해서 야매풀이같다는 생각이 들었는데, submissions를 보면 비슷하게 접근한 풀이들이 많았다. 
• reverse나 [::-1]을 사용하지 않고 Collections 모듈의 deque를 사용한 경우도 있었다. 
• appendleft 메소드를 사용해서 레벨 결과를 앞쪽에 추가해서 굳이 [::-1]이나 reverse를 통해 순서를 뒤집을 필요가 없어진다. 
  
  • 추가적으로 helper 함수를 써서, 재귀를 돌린 위의 방식과 달리,
  • root자체를 deque에 쌓아두고, q에 값이 있을 동안 for문을 돌리면서, popleft한 값을 level에 append하는 식으로 level별 node list를 만든다음에, 
  • res list의 가장 왼쪽에 해당 list를 append하는 식으로 작성되어있다.

# 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 levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = deque()
        if not root:
            return res
        q = deque()
        q.append(root)
        while q:
            level = []
            for i in range(len(q)):
                curr = q.popleft()
                level.append(curr.val)
                if curr.left:
                    q.append(curr.left)
                if curr.right:
                    q.append(curr.right)
            if level:
                res.appendleft(level)
        return res

5. 배운 점

• deque
• 언젠가 deque를 사용해서 문제 풀어보기!