[스파르타] 99클럽 2기 코테스터디 15일차 TIL / leet 2415

LeetCode: 2415. Reverse Odd Levels of Binary Tree  (링크)

2415. Reverse Odd Levels of Binary Tree

 

백준에 너무 익숙해지다 보니 당연히 input으로 주어진 값이 리스트일 것이라고 당연하게 생각하고 풀이를 시작했다. 그래서 트리 노드의 특성을 전혀 살리지 못하고 2의 몇 승인지에 따라 리스트 슬라이싱을 계산했다. 그러나 실제 코드에서는 len(root) 자체가 불가능하여 풀이를 새로 작성해야 했다. 문제에 대해 설명한 유튜브를 봤는데 스위칭 방식이 간단해서 이를 참고하여 풀었다. 예를 들어 홀수 레벨의 노드가 [1, 2, 3, 4, 5, 6]이라면 최종적으로 [6, 5, 4, 3, 2, 1]로 변경되어야 하며, 각 노드의 위치가 항상 동일하게 대응된다. 즉, (1, 6), (2, 5), (3, 4)처럼 각 노드 1, 2의 left, right가 서로 대응되므로 이 방식을 다른 레벨에도 적용하면 된다.

## 잘못된 풀이
class Solution:
    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        depth = int(math.log2(len(root))
        ans = []
        for i in range(depth+1):
            temp = root[2**i-1:2**(i+1)-1]
            if i % 2 != 0:
                temp = temp[::-1]
                ans.extend(temp)
            else:
                ans.extend(temp)
        return ans
        
        
## 참고한 풀이
# 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 reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def helper(root1, root2, depth):
            if root1 is None and root2 is None:
                return None

			# 홀수번째라면 스위치
            if depth % 2 != 0:
                root1.val, root2.val = root2.val, root1.val
            
            # 다음 레벨로 가서 대응되는 노드를 찾음
            helper(root1.left, root2.right, depth + 1)
            helper(root1.right, root2.left, depth + 1)
        
        # 초기 시작 노드
        helper(root.left, root.right, 1)
        return root

오늘 미들러 풀이 끝!

---

참고한 풀이: https://www.youtube.com/watch?v=AsSsyupOZXU