LeetCode: 103번 (Binary Tree Zigzag Level Order Traversal) [JAVA]

문제 링크

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

Binary Tree Zigzag Level Order Traversal - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 레벨 별로 노드를 넣을 List<List<Integer>> answer 자료구조 생성
2. 재귀 기반의 순회 함수 생성 (인자는 노드와, 노드의 레벨을 나타내는 정수)
   1) 인자로 들어온 노드가 null이라면 return
   2) List<List<Integer>> answer에서 현재 레벨의 List가 생성되지 않았다면, 새로운 List를 초기화해 삽입
   3) 노드의 왼쪽에 대해 재귀함수를 호출 (레벨+1)
   4) 현재 노드의 값을 해당 레벨의 List에 삽입. 단, 이 때 주어진 level이 짝수면 list의 마지막에 값을 삽입하고, level이 홀수라면 list의 처음에 값을 삽입
   5) 노드의 오른쪽에 대해 재귀함수를 호출 (레벨+1)
3. 앞서 구현한 재귀함수를 주어진 루트 노드를 인자로 호출하고, 그 결과 answer를 반환

 바로 이전 번호 문제인 102번(Binary Tree Level Order Traversal)과 매우 유사한 문제이다. 앞선 문제와 달라진 점이라면, 레벨별로 노드를 넣는 과정에 있어서 레벨에 따라 순서를 정방향으로 하거나 역방향으로 구성해야 하는 점이다.
 전체적으로 풀이도 동일하다. 다만 재귀함수에서 노드를 넣는 과정에서만 약간 달라진다. 만약 인자로 들어온 레벨값이 짝수라면 현재 레벨 리스트에 노드의 값을 순서대로 넣으면 되고, 레베값이 홀수라면 현재 레벨 리스트의 노드의 값을 0번째로 넣어 순서가 역방향이 되도록 넣으면 된다.

 

class Solution {
    List<List<Integer>> answer = new ArrayList<>();

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        zigzagLevelTraversal(root, 0);

        return answer;
    }

    void zigzagLevelTraversal(TreeNode node, int level){
        if (node == null) {
            return;
        }

        if (answer.size() == level) {//해당 레벨에 대한 List가 생성되지 않았다면 생성
            answer.add(new ArrayList<>());
        }

        zigzagLevelTraversal(node.left, level + 1);

        if (level % 2 == 0) {//짝수 레벨이라면 순서대로
            answer.get(level).add(node.val);
        } else {//홀수 레벨이라면 그 반대로
            answer.get(level).add(0, node.val);
        }

        zigzagLevelTraversal(node.right, level + 1);
    }
}

결과