99클럽 코테 스터디 9일차 TIL [LeetCode] Reverse Odd Levels of Binary Tree (Java)

문제

[LeetCode] Reverse Odd Levels of Binary Tree

풀이

이진 트리에서 홀수 레벨의 노드 값을 반대로 뒤집는 문제

• BFS(너비 우선 탐색)를 사용하여 트리를 레벨 순서로 탐색한다.
  • i는 트리 레벨을 의미
  • k는 각 레벨의 노드 개수를 의미
• 큐를 사용하여 각 레벨의 노드를 탐색한다.
  • i가 홀수인 경우, t에 노드 추가
• 리스트를 사용하여 노드 값을 임시로 저장한 뒤 뒤집는다.

정답 코드

class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        for (int i = 0; !q.isEmpty(); ++i) {
            List<TreeNode> t = new ArrayList<>();
            for (int k = q.size(); k > 0; --k) {
                TreeNode node = q.poll();
                if (i % 2 == 1) {
                    t.add(node);
                }
                if (node.left != null) {
                    q.offer(node.left);
                    q.offer(node.right);
                }
            }
            for (int l = 0, r = t.size() - 1; l < r; ++l, --r) {
                int x = t.get(l).val;
                t.get(l).val = t.get(r).val;
                t.get(r).val = x;
            }
        }
        return root;
    }
}

다른 풀이

DFS(깊이 우선 탐색)를 사용

class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        dfs(root.left, root.right, 1);
        return root;
    }

    void dfs(TreeNode L, TreeNode R, int level) {
        if (L == null || R == null) return;

        if (level % 2 == 1) {
            int temp = L.val;
            L.val = R.val;
            R.val = temp;
        }

        dfs(L.left, R.right, level + 1);
        dfs(L.right, R.left, level + 1);
    }
}