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

문제 링크

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

Binary Tree Level Order Traversal - LeetCode

풀이

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

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

 주어진 문제에서 레벨 순회가 언급되기 때문에, Queue 자료구조를 기반으로 한 레벨 순회를 직접 구현해야 할 것 같지만 그럴 필요가 없는 문제이다. 문제에서 레벨별로 다른 리스트에 값들을 모아 반환하면 되기 때문에, 레벨별로 호출 순서만 맞추면 되는 문제기 때문이다.
 우선 노드 값들을 저장하기 위한 List<List<Integer>> answer를 초기화한다. 그 다음에는 바로 순회를 하는 재귀 기반의 함수를 구현하면 되는데, 인자로는 특정 노드와 해당 노드의 레벨을 나타내는 정수를 받으면 된다. 만약 주어진 노드가 null이라면 바로 return을 한다. 또 앞서 초기화한 answer의 size가 현재 레벨과 같다면, 이는 해당 레벨에 노드 값들을 담을 List가 생성되지 않았다는 뜻이기 때문에 answer에 새로운 List를 삽입해준다.
 그리고는 실질적 처리를 진행하면 된다. 레벨별 호출 순서를 맞추기 위해, 노드의 왼쪽 자식 노드를 먼저 처리해준다. 이때 동일한 재귀함수를 왼쪽 자식 노드에 대해 레벨+1을 해 호출한다. 그 다음엔 현재 노드에 대해, answer의 현재 레벨 리스트에 노드의 값을 넣어준다. 마지막으로 오른쪽 자식 노드에 대해서도 동일한 재귀함수를 호출해주면 된다.
 이처럼 재귀 함수를 구현이 완료되면, 문제에서 인자로 받은 트리의 루트 노드를 재귀함수에 넣어 호출해준 다음, 결과 answer를 반환해주면 된다.

 

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

    public List<List<Integer>> levelOrder(TreeNode root) {
        levelTraversal(root, 0);
        return answer;
    }

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

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

        levelTraversal(node.left, level + 1);//

        answer.get(level).add(node.val);

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

결과