99클럽 코테 스터디 13일차 TIL + DFS(Deepest Leaves Sum)

오늘의 과제

리트코드 Medium으로 분류된 Deepest Leaves Sum입니다.

 

어제에 이어 문제의 유형은 깊이/너비 우선 탐색(DFS/BFS) 입니다.

문제

https://leetcode.com/problems/deepest-leaves-sum/description/

 

먼저 문제 요구사항 요약입니다.

 

입력으로 아래와 같은 TreeNode 객체가 주어집니다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

 

주어진 트리 노드 중 가장 깊은 곳에 있는 말단 노드들의 합을 구해 반환해주면 됩니다.

 

자식 노드가 없는 말단 노드는 바로 찾을 수 있으나

순회마다 가장 깊은 곳인지 판단하기가 어려울 것 같아 DFS를 두 번 돌렸습니다.

 

첫 번째 DFS를 통해 가장 깊은 곳의 Level을 찾고,

두 번째 DFS를 통해 가장 깊은 곳의 Level에 도달했다면 해당 노드의 값을 합산하였습니다.

 

아래는 코드입니다.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

import java.util.*;

class Solution {
    // 1. 제일 깊은 곳 찾기
    // 2. 깊은 곳 노드 밸류 합산
    int deepest = Integer.MIN_VALUE;
    int sum = 0;

    public int deepestLeavesSum(TreeNode root) {
        findDeepest(root, 0);
        sumDeepestNodeValue(root, 0);
        return sum;
    }

    private void findDeepest(TreeNode node, int level) {
        if (node.left == null && node.right == null) {
            deepest = Math.max(deepest, level);
            return;
        }
        if (node.left != null) findDeepest(node.left, level + 1);
        if (node.right != null) findDeepest(node.right, level + 1);
    }

    private void sumDeepestNodeValue(TreeNode node, int level) {
        if (level == deepest) {
            sum += node.val;
            return;
        }
        if (node.left != null) sumDeepestNodeValue(node.left, level + 1);
        if (node.right != null) sumDeepestNodeValue(node.right, level + 1);
    }
}

 

배운 점

 

처음에 deepest와 sum을 습관처럼 static으로 선언해 왜맞틀을 시전했습니다.

 

프로그래머스나 백준 같은 경우는 static으로 선언해도 매번 다시 메모리에 적재해주는 것 같았으나

리트코드는 그저 단순 반복 실행인 것 같습니다.

 

다 풀어놓고 static으로 인해 삽질하기는 했으나 무난히 풀려 다행입니다.

 

프로그래머스의 다른 사람 정답보기처럼 리트코드는 성능별 대표 답안을 공개해줍니다.

 

 

 

사실 DFS를 두 번 쓰는 시점에 조금 더 최적화는 가능하겠구나 생각은 했으나 역시 최선의 방법은 아니였습니다.

 

정답 코드를 간략히 살펴보면

void deepest(TreeNode root, int level){
        if(root == null) return;
        if(level > maxlevel){
            maxlevel=level;
            sum = root.val;
        }else if(level == maxlevel && root.left == root.right){
            sum+=root.val;
        }
        deepest(root.left, level+1);
        deepest(root.right, level+1);
    }

 

위 코드에서 maxLevel이 갱신되면 sum을 해당 노드 값으로 초기화 해주는점,

root.left == root.right를 통해 말단 노드를 판단한점이 놀라웠습니다.

 

앞으로 풀이 말고도 다른 사람의 풀이를 보며 결과물을 만들어내는

다양한 선택지를 학습하는 노력이 더 필요할 것 같습니다.

 

 

오늘의 한줄평

목적지로 향하는 길은 매우 많다. 상황에 맞게 길을 선택하려면 많은 길을 가봐야한다.