BFS를 활용한 알고리즘 문제풀이

오늘 푼 문제: 2415. Reverse Odd Levels of Binary Tree

입출력

• 입력: 포화 이진 트리가 주어집니다.
• 출력: 홀수 레벨의 노드들의 값을 반대로 할당한 포화 이진 트리를 반환합니다.

예제 코드

import java.util.*;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * 1. 레벨 단위로 노드를 탐색한 후 해당 레벨이 홀수일 경우 해당 노드의 순서를 바꾼다.
     */
    public TreeNode reverseOddLevels(TreeNode root) {
        int level = 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            System.out.println("level = " + level);
            int size = q.size();
            // 홀수 레벨일 경우 해당 노드들의 값을 바꾼다.
            if (level % 2 != 0) {
                List<Integer> vals = new ArrayList<>();
                for (TreeNode t : q) vals.add(t.val); // 해당 레벨의 모든 값들을 리스트에 저장한다.
                Collections.reverse(vals); // 해당 리스트를 역순으로 바꾼 뒤 노드의 값에 할당해준다.
                int idx = 0;
                for (TreeNode tn : q) tn.val = vals.get(idx++);
            }
            for (int i = 0; i < size; i++) {
                    TreeNode tn = q.poll();
                    if (tn.left != null) q.offer(tn.left);
                    if (tn.right != null) q.offer(tn.right);
            }
            level++;
        }
        return root;
    }
}

• BFS를 활용하여 포화 이진 트리를 레벨별로 탐색합니다.
• 레벨별로 탐색이 끝날 경우 int level을 증가시킵니다.
• 홀수 레벨일 경우 Queue에 있는 모든 노드의 val을 순서대로 list에 저장합니다.
• 그 후 Collections.reverse()를 활용하여 역순으로 정렬한 후 각 노드에 값을 할당합니다.

회고

• 뭔가 Runtime도 메모리 사용도 제 코드는 아쉽네요...
• 다른 분들의 코드를 보면서 고민해봐야할 것 같습니다.