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

문제 링크

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

Binary Tree Level Order Traversal II - LeetCode

풀이

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

1. 주어진 트리의 최대 레벨을 확인하고, 해당 레벨 수 만큼 List<List<Integer>> answer를 초기화
2. 재귀 기반의 순회 함수 생성 (인자는 노드, 현재 노드의 레벨을 나타내는 정수, 전체 트리의 최대 레벨
   1) 노드가 null이라면 return
   2) 현재 노드의 왼쪽에 대해 동일 재귀함수를 호출
   3) 트리 최대 레벨 - 현재 노드 레벨의 결과를 인덱스로, List<List<Integer>>인 answer에 현재 노드 값을 삽입
   4) 현재 노드의 오른쪽에 대해 동일 재귀함수를 호출
3. 주어진 root를 인자로 앞선 순회 함수 호출 후, answer를 반환

 앞서 해결한 102번(Binary Tree Level Order Traversal)에서 약간만 변경된 문제이다. 102번 문제의 경우 레벨 값을 그대로 인덱스로 삼아 자료구조에 노드 값을 넣었다면, 현재 문제에선 List<List<Integer>> 속 노드 값들이 레벨의 역순으로 담겨져야 하기 때문에, 우선적으로 트리의 최대 레벨을 구한 다음 (최대 레벨 - 현재 레벨)의 값을 인덱스 삼아 List<List<Integer>>에 넣어주면 된다.
 우선 노드 값들을 저장하기 위한 List<List<Integer>> answer를 선언해준다. 그 다음 주어진 노드 root를 바탕으로 트리의 최대 레벨 값을 구해낸 다음, 해당 최대 레벨만큼 answer에 ArrayList를 미리 추가해 초기화해준다.
 그 다음에는 순회를 위한 재귀 함수를 구현한다. 인자로는 노드, 현재 노드의 레벨을 나타내는 정수, 트리의 최대 레벨 값을 받는다. 주어진 노드가 null이라면, 별다른 로직 없이 바로 return 한다. 그 다음에는 현재 노드의 왼쪽 자식 노드에 대해 동일한 재귀 함수를 호출해준다. 그리고 현재 노드 값에 대해, answer 속 (트리 최대 레벨 - 현재 노드 레벨)을 인덱스로 삼아 해당 위치에 존재하는 ArrayList에 접근하여 그 곳에 해당 노드 값을 삽입해준다. 마지막으로 현재 노드의 오른쪽 자식 노드에 대해 동일한 재귀 함수를 호출해주면 된다.
 이렇게 함수를 구현하고 나서는, 주어진 root 노드에 대해 해당 함수를 호출하고, 결과가 저장된 answer를 반환하면 된다.

 

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

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        int maxLevel = checkMaxLevel(root, 1);//트리 최대 레벨 체크

        for (int i = 0; i < maxLevel; i++) {//최대 레벨 만큼 미리 초기화
            answer.add(new ArrayList<>());
        }

        levelTraversal(root, 1, maxLevel);

        return answer;
    }

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

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

        answer.get(maxLevel - level).add(node.val);//최대 레벨 - 현재 레벨 위치의 ArrayList에 노드 값 삽입

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

    int checkMaxLevel(TreeNode node, int level) {//트리 최대 레벨 확인
        if (node == null) {
            return level - 1;
        }

        return Math.max(checkMaxLevel(node.left, level + 1), checkMaxLevel(node.right, level + 1));
    }
}

결과