99클럽 코테 스터디 13일자 TIL + Deepest Leaves Sum

문제 출처

https://leetcode.com/problems/deepest-leaves-sum/ (leetcode)

학습 키워드

DFS/BFS

시도 방법

(1) 기존 TreeNode에 depth기능을 추가한 클래스를 구현
(2) TreeMap을 이용해서 depth 별 합계를 구현

내가 작성한 코드

 import java.util.Queue; 
 import java.util.LinkedList; 
 import java.util.TreeMap; 

class Solution {
    public int deepestLeavesSum(TreeNode root) {

     Queue<TreeExtension> queue = new LinkedList<>();
     TreeMap<Integer , Integer> sumByDepth = new TreeMap<>(); 

     queue.offer(new TreeExtension(1 , root)); 

     while(!queue.isEmpty()) {

        TreeExtension now = queue.poll(); 
        
        if(sumByDepth.get(now.depth) == null) {
            sumByDepth.put(now.depth , now.node.val); 
        } else {
            sumByDepth.put(now.depth , sumByDepth.get(now.depth) + now.node.val); 
        }

        if(now.node.left != null) queue.add(new TreeExtension(now.depth+1, now.node.left)); 
        if(now.node.right != null) queue.add(new TreeExtension(now.depth+1, now.node.right)); 
        
     }
    
    return sumByDepth.get(sumByDepth.lastKey());
    }
}

class TreeExtension {
    
    int depth; //해당 트리의 depth정보
    TreeNode node ; 

    public TreeExtension(int depth , TreeNode node) {
        this.depth = depth; 
        this.node = node; 
    }
}

코드설명

(1) TreeExtension 클래스를 이용해 기존 TreeNode 와 추가로 depth 정보를 저장할 수 있도록 클래스를 추가했다.

(2) bfs 기법을 통해 만약 현재 node 기준 하위 노드가 left 나 right에 있다면 depth를 하나 추가한 새로운 TreeExtension 를 큐에 추가했다.

(3) 큐에서 하나씩 꺼내면서 해당 node의 값(val)을 TreeMap의 키를 이용해서 각각 더했다. (왜냐면 가장 깊은 depth를 찾을려고 bfs 사용하고 또 합계를 구하기 위해서 bfs를 쓰면 중복이라는 생각이 들었기 때문이다.)

(4) 결과저으로 TreeMap 내부에 KEY , VALUE 형태로 데이터가 저장되었고
TreeMap은 자동으로 key를 기준 정렬하기 때문에 가장 마지막의 key == 가장 깊은 depth 임을 의미해 마지막 key의 value를 리턴해 정답 처리 되었다.

출력결과

새롭게 알게된 점

TreeMap은 HashMap과 달리 key를 기준으로 자연 정렬을 해준다.
그렇기 때문에 가장 마지막 key가 가장 깊은 depth라는 아이디어를 활용해 문제를 풀었고 이때 lastKey() 라는 메서드를 활용하면 가장 마지막 key 정보를 추출할 수 있다는 것을 알았다.

다음에 풀어볼 문제 - ??

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL