[코딩테스트 일지 - 99클럽] 7일차 - Deepest Leaves Sum

코딩 테스트 준비 일지 7 일차

• 응시 사이트 : LeetCode

• 문제 : Deepest Leaves Sum

• 난이도 : 중하

Given the root of a binary tree, return the sum of values of its deepest leaves.

Example 1:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

Example 2:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 19

Constraints:

• The number of nodes in the tree is in the range [1, 104].

• 1 <= Node.val <= 100

문제 풀이 접근

이전에 타겟넘버와 같은 DFS / BFS 유형을 볼 때 이런 느낌의 트리노드들을 어떻게 더할지, 이런 부분에 대해서 이해하고 넘어가서 비교적 쉬웠다 시간으로만 보면 31분 정도 걸렸다. 이것저것 하다보니...

그림과 제목을 보자마자, 아! 이거 그냥 끝단에 위치한 변수끼리 더해주면 되네! 라는 느낌을 받았고, 문제와 입출력으로 확신했다.

문제 해결 플로우는 아래와 같다.
1. root 가 주어지고 왼쪽 오른쪽을 노드로 입력해서 준다. 즉, Depth 값에 대한것은 줄 생각이 없다.
2. 고로 내가 Depth 값을 유추하는 로직을 돌려서 Depth 값을 가진 Value와 매칭해서 저장해 놓는다.
3. 이후 데이터 세팅이 끝나면 내 Depth 값이랑 동일한 value 가져와서 더해서 리턴한다.
이 정도 까지 풀이 유추를 했으면 문제 다풀었다.

정답 작성 코드 ( C# )

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
public static int s_iFindDepth; // 깊이 값
public List<KeyValuePair<int, int>> depthValueList = new List<KeyValuePair<int, int>>(); // 깊이값에 대한 Value 값을 나타내기 위한 변수

public int DeepestLeavesSum(TreeNode root)
{
    int resValue = 0;
    s_iFindDepth = 0; // 으로 초기화

    DFS(root, 0);

    var findPair = depthValueList.FindAll(rhs => rhs.Key == s_iFindD
    for (int i = 0; i < findPair.Count; ++i)
    {
        var Value = findPair[i].Value;
        resValue += Value;
    }

    return resValue;
}

public void DFS(TreeNode node, int depth) // 깊이 값
{
    if (s_iFindDepth < depth)
    {
        s_iFindDepth = depth; // Depth 값이 더 크다면 
    }

    int value = node.val;

    depthValueList.Add(new KeyValuePair<int, int>(depth, value));

    if (node.left != null)
        DFS(node.left, depth + 1);

    if (node.right != null)
        DFS(node.right, depth + 1);
}

코드 결과

프로젝트에서 바로 돌릴 수 있는 코드 ( C# )

TC1 번에 한해서 돌려볼 수 있는 코드다. 위의 구성만 바꾸면 2도 되고 다른 구성도 가능하다.

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Runtime.InteropServices;
using System.Security.Authentication;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Web;
using System.Xml.Linq;/*URL : https://leetcode.com/problems/deepest-leaves-sum/
*/namespace CodingTestProj
{
internal class Program
{
static void Main(string[] args)
{
// TC1.
// Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
// Output: 15        TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
TreeNode node8 = new TreeNode(8);    node1.left = node2;
    node1.right = node3;

    node2.left = node4;
    node2.right = node5;

    node3.left = null;
    node3.right = node6;

    node4.left = node7;
    node4.right = null;

    node5.left = null;
    node5.right = null;

    node6.left = null;
    node6.right = node8;

    Solution solution = new Solution(); ;
    int result = solution.DeepestLeavesSum(node1);
    Console.WriteLine(result);
}

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution
{

    public static int s_iFindDepth; // 깊이 값
    public List<KeyValuePair<int, int>> depthValueList = new List<KeyValuePair<int, int>>(); // 깊이값에 대한 Value 값을 나타내기 위한 변수

    public int DeepestLeavesSum(TreeNode root)
    {
        int resValue = 0;
        s_iFindDepth = 0; // 으로 초기화

        DFS(root, 0);

        var findPair = depthValueList.FindAll(rhs => rhs.Key == s_iFindDepth);
        for (int i = 0; i < findPair.Count; ++i)
        {
            var Value = findPair[i].Value;
            resValue += Value;
        }

        return resValue;
    }

    public void DFS(TreeNode node, int depth) // 깊이 값
    {
        if (s_iFindDepth < depth)
        {
            s_iFindDepth = depth; // Depth 값이 더 크다면 
        }

        int value = node.val;

        depthValueList.Add(new KeyValuePair<int, int>(depth, value));

        if (node.left != null)
            DFS(node.left, depth + 1);

        if (node.right != null)
            DFS(node.right, depth + 1);
    }
}}}