[LeetCode] 2415 Reverse Odd Levels of Binary Tree

💡 오늘의 학습 키워드

📌  완전 이진 트리

 

문제 설명

문제 링크 : https://leetcode.com/problems/reverse-odd-levels-of-binary-tree/

Given the root of a perfect binary tree, reverse the node values at each odd level of the tree.
For example, suppose the node values at level 3 are [2,1,3,4,7,11,29,18],
then it should become [18,29,11,7,4,3,1,2].
Return the root of the reversed tree.
A binary tree is perfect if all parent nodes have two children and all leaves are on the same level.
The level of a node is the number of edges along the path between it and the root node.

제한 사항
1. The number of nodes in the tree is in the range [1, 2^14].
2. 0 <= Node.val <= 10^5
3. root is a perfect binary tree.

 

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

완전 이진 트리의 홀수 레벨 노드 값을 조정하는 문제입니다. 
다양한 문제 풀이들을 볼 수 있었고 도움이 되었던 코드들을 참조하여 모두 보려고 합니다.
트리를 이해하는 가장 기본적인 문제 풀이 과정은 다음과 같습니다. 

1. 트리를 레벨 별로 순회하여 노드를 리스트에 저장합니다.
2. 짝수 레벨이면 노드 순서를 그대로, 홀수 레벨이면 노드 순서를 뒤집어 nodes 리스트에 저장합니다.
3. 다음 레벨 노드로 level 리스트를 업데이트 합니다.
4. 각 레벨의 노드가 nodes 리스트에 저장된 후 각 노드의 자식 포인터를 재설정합니다.
5. 루트 노드를 반환하여 수정된 트리를 반환합니다.

 

비교, 순회를  이용한 포인터 재설정 방법이 가장 트리 구조를 이해하는데  직관적인 풀이 방식이었습니다.
변경된 노드를 리스트에 저장하고 짝수 레벨의 값을 변경된 홀수 레벨에 맞게 재조정하는 과정과
루트 노트를 반환하면 수정된 전체 트리를 반환할 수 있다는 점을 이해한다면 풀이에 문제는 없었습니다.

 

이 방식을 통해 트리 구조를 이해하였다면 시간 복잡도를 줄일 수 있는 방법을 고려해보아야 합니다.
단순 비교, 순회를 이용한 포인터 재설정 방법과 비교해 재귀, 큐 자료구조를 사용해 문제를 풀어냈다면
메모리 사용을 최적화하고 코드를 더 간결하게 수정할 수 있습니다.

 

재귀 함수를 사용한다면 두 노드와 현재 레벨을 인자로 받아 재귀로 홀수 레벨의 값을 뒤집는 풀이가 가능합니다.
큐 자료구조를 사용한다면 레벨 순서로 트리를 순회하면서 현재 레벨 노드의 자식 노드를 큐에 추가하는 풀이가 가능합니다.

 

이러한 자료구조를 사용할 때에는 각 자료구조의 장,단점을 잘 고려하여 풀이를 진행해야 합니다.
예를 들어, 재귀 깊이가 깊지 않은 트리에서는 재귀적 접근이 더 간결할 수 있고, 매우 큰 트리에서는 큐를 이용한 
반복적 접근이 더 안전할 수 있습니다. 

 

💡 내가 해결한 방식은?

레벨 순서 순회 + 포인터 재설정 이용한 풀이 (1261ms)

class Solution:
	def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    	# 1. Level order Traversal
        nodes = []
        level = [root]
        idx = 0
        
        while level:
            # 노드 레벨이 짝수일 경우 -> 기존 값 저장
            # 노드 레벨이 홀수일 경우 -> 역순 값 저장
        	if idx % 2 == 0:
            	nodes.append(level)
            else:
            	nodes.appdend(level[::-1])
            
            # 다음 레벨 노드로 level 리스트 업데이트
            # level = [child for node in level for child in (node.left, node.right) if child]
            next_level = []
            for node in level:
            	if node.left:
                	next_level.append(node.left)
                if node.right:
                	next_level.append(node.right)
            level = next_level
            
            idx += 1
            
        # 2. Node Repointing
        for i in range(len(nodes) - 1):
        	for j in range(len(nodes[i])):
            	nodes[i][j].left = nodes[i+1][2*j]
                nodes[i][j].right = nodes[i+1][2*j+1]
                
        return nodes[0][0]

재귀를 이용한 풀이 (664ms)

class Solution:
	def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    	def reverse_levels(left, right, level):
        	if not left or not right:
            	return
            if level % 2 == 1:
            	left.val, right.val = right.val, left.val
            reverse_levels(left.left, right.right, level + 1)
            reverse_levels(left.right, right.left, level + 1)
            
        if not root:
        	return root
        reverse_levels(root.left, root.right, 1)
        return root

Queue를 사용한 반복적 접근 (627ms)

class Solution:
	def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    	if not root:
        	return root
        
        queue = deque([root])
        level = 0
        
        while queue:
        	level_size = len(queue)
            curr_level = []
            for _ in range(level_size):
            	node = queue.popleft()
                curr_level.append(node)
                if node.left:
                	queue.append(node.left)
                if node.right:
                	queue.append(node.right)
                
            if level % 2 == 1:
            	for i in range(level_size // 2):
                	curr_level[i].val, curr_level[level_size-1-i].val = curr_level[level_size-1-i].val, curr_level[i].val
                    
            level += 1
            
        return root

 

---

✍️  TIL

이번 문제에서 첫번째 고비는 매개변수의 저 Optional[TreeNode] 를 이해하는 것었다. 
일단 Optional 은 None 값이 들어갈 수 있을 때 사용한다.
print(root)를 하면 다음의 값이 나오는데 안보는게 문제 풀이에 도움이 되었겠다..싶었다.

TreeNode{val: 2, left: TreeNode{val: 3, left: TreeNode{val: 8, left: None, right: None}, right: TreeNode{val: 13, left: None, right: None}}, right: TreeNode{val: 5, left: TreeNode{val: 21, left: None, right: None}, right: TreeNode{val: 34, left: None, right: None}}} [TreeNode{val: 2, left: TreeNode{val: 3, left: TreeNode{val: 8, left: None, right: None}, right: TreeNode{val: 13, left: None, right: None}}, right: TreeNode{val: 5, left: TreeNode{val: 21, left: None, right: None}, right: TreeNode{val: 34, left: None, right: None}}}]

결국 아래의 값들을 포함한 root 값만 level 리스트에 추가한다고 생각하면 간단한 풀이가 되었다.
(완전 이진 트리에 대한 이해와 이를 코드로 다룰 줄 알고 적절한 자료구조를 선택할 수 있다면) 간단한 풀이..
내가 사용한 방식의 시간 복잡도를 큐를 사용할 때 절반이나 줄어드는 것을 본다면 자료구조의 사용이 얼마나 중요한지 알 수 있을 것이다.