99클럽 코테 스터디 12일차 TIL + deque, BFS

 

🔗 LeetCode - 2415. Reverse Odd Levels of Binary Tree

이제 deque 쓰는 건 완전 익숙해짐!

이 문제는 홀수 층에 있는 노드들을 reverse 해주는 것인데 내가 쓴 방법은

처음에 트리를 돌면서 각 층에 해당하는 노드를 리스트에 저장해 놓고

두번째로 트리를 돌면서 각 층에 해당하는 노드를 pop 해줘서 reverse 되도록 했다. 

그리고 리트 코드는 리스트가 아니라 객체(TreeNode)가 input, output이다.

근데 사이트로 테스트를 하자니 제한도 있고 시간도 오래걸려서

이전에 삽질하다가 만들어 놓은 리스트 -> 트리 로 만드는 코드를 유용하게 썼다. 야호

from collections import deque

class Solution:

    def reverseOddLevels(self, root):
        odd_dict = {}
        depth = 0
        queue = deque()
        queue.append((root, depth))

        # tree를 순회하면서 odd 층에 있는 value를 수집해 odd_dict에 넣음
        while queue:
            node, depth = queue.popleft()
            if depth % 2 == 0 and node.left:
                try:
                    odd_dict[depth + 1] += [node.left.val]
                    odd_dict[depth + 1] += [node.right.val]
                except KeyError:
                    odd_dict[depth + 1] = [node.left.val]
                    odd_dict[depth + 1] += [node.right.val]
            # perfect best 여서 한쪽만 체크
            if node.left:
                queue.append((node.left, depth + 1))
                queue.append((node.right, depth + 1))

        # tree를 다시 순회하면서 odd 층에 val 값 바꿔줌
        depth = 0
        queue = deque()
        queue.append((root, depth))
        while queue:
            node, depth = queue.popleft()
            if depth % 2 == 0 and node.left:
                node.left.val = odd_dict[depth + 1].pop()
                node.right.val = odd_dict[depth + 1].pop()
            # perfect best 여서 한쪽만 체크
            if node.left:
                queue.append((node.left, depth + 1))
                queue.append((node.right, depth + 1))
                depth += 1
        return root