[Leet Code] Binary Tree Level Order Traversal

안녕하세요!
서류를 적기 싫어서.. 알고리즘을 풀어온 저입니다 ㅎㅎ
오늘은 5월 3주차 6번째 알고리즘인 Binary Tree Level Order Traversal 풀이를 작성해보겠습니다.

문제

요약
주어진 Binary Tree 에서 level 별로 node 의 value 를 리스트에 넣어서 return하는 문제입니다.

처음 생각한 방법

dfs 알고리즘을 활용해서 level 을 증가할수록 리스트에 value 를 저장하는 방식을 사용했습니다.

처음 생각한 방식으로 Accept를 받았습니다.
알고리즘 공부하기 전에는 트리 문제가 나오면 엄청 힘들었었는데, 지금은 나름 생각하고 풀 수 있게된 것 같아서 뿌듯하네요 >.<
이제 코드를 설명하도록 하겠습니다.

코드 설명

List<List<Integer>> result;

전역으로 return할 result 를 선언합니다.

result = new ArrayList<>();
dfs(root, 0);

솔루션 함수에서 result 를 초기화해주고 dfs 함수를 실행합니다.

dfs 함수

private void dfs(TreeNode node, int index) {
    if (node == null) return;

    if (result.size() <= index) result.add(new ArrayList<>());
    result.get(index).add(node.val);

    dfs(node.left, index + 1);
    dfs(node.right, index + 1);
}

Binary Tree 와 트리의 레벨을 의미하는 index 를 인자로 받습니다.
**dfs 의 종료 조건은 node 가 없을 때 return**합니다.

result 를 ArrayList 로 선언했기 때문에 size 가 index 보다 작거나 같다는 것은 아직 해당 레벨의 노드를 리스트에 추가하지 않았다는 것을 의미합니다.
그래서 해당 경우에는 new ArrayList<>() 를 add 했습니다.
그것이 아니라면 해당 레벨의 노드가 적어도 하나가 저장되어있다는 것이므로, index 로 접근해서 node.val 를 저장해줍니다.

그리고 아래 레벨로 내려가면서 node.val 을 저장하기 위해 dfs 함수를 재귀호출해줍니다.

전체 코드

class Solution {
    List<List<Integer>> result;

    public List<List<Integer>> levelOrder(TreeNode root) {
         result = new ArrayList<>();
         dfs(root, 0);

         return result;
    }

    private void dfs(TreeNode node, int index) {
        if (node == null) return;

        if (result.size() <= index) result.add(new ArrayList<>());
        result.get(index).add(node.val);

        dfs(node.left, index + 1);
        dfs(node.right, index + 1);
    }
}

마무리

현재 시간이 새벽 2시가 조금 넘은 시간인데, 나름 수월하게 푼 문제라서 다행입니다.
만약 어려운 문제였다면,, 새벽부터 좌절하고 잠에 들었을 것 같네요.

이번 포스팅도 읽어주셔서 감사합니다 :) 질문이나 피드백은 언제나 환영이에요!