[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시가 조금 넘은 시간인데, 나름 수월하게 푼 문제라서 다행입니다.
만약 어려운 문제였다면,, 새벽부터 좌절하고 잠에 들었을 것 같네요.

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