99클럽 코테 스터디 13일차 TIL - 1302. Deepest Leaves Sum

오늘의 학습 키워드

• 깊이우선탐색(DFS)

오늘의 회고

1. 문제

[leetcode] 문제 URL

2. 해결 방안

class Solution {
    public int deepestLeavesSum(TreeNode root) {
        int depth = 0;

        Queue<Node> que = new LinkedList<>();
        que.add(new Node(root, 0));

        Node tmp;
        TreeNode right_node;
        TreeNode left_node;
        while(!que.isEmpty()){
            tmp = que.poll();
            depth = Math.max(depth, tmp.cnt);

            right_node = tmp.treeNode.right;
            if(right_node !=null) que.add(new Node(right_node,tmp.cnt+1));
            left_node = tmp.treeNode.left;
            if(left_node !=null) que.add(new Node(left_node,tmp.cnt+1));
        }

        //while에서 빠져나온 depth가 가장 깊은 길이
        que.clear();
        que.add(new Node(root, 0));
        int total_sum = 0;
        while(!que.isEmpty()){
            tmp = que.poll();

            if(tmp.cnt==depth) total_sum += tmp.treeNode.val;
            right_node = tmp.treeNode.right;
            if(right_node !=null) que.add(new Node(right_node,tmp.cnt+1));
            left_node = tmp.treeNode.left;
            if(left_node !=null) que.add(new Node(left_node,tmp.cnt+1));

        }


        return total_sum;        
    }
    
    
    public static class Node{
        TreeNode treeNode;
        int cnt;

        public Node(TreeNode treeNode, int cnt){
            this.treeNode = treeNode;
            this.cnt = cnt;
        }
    }    
}

3. 피드백

• 깊이 우선 탐색. 코드 다시 작성해보고 추가 예정.

4. 새로 알게된 것