[코테연습] Deepest Leaves Sum

오늘은 Leetcode 사이트의 이진트리 검색 관련 문제를 풀어보았다. 

 

https://leetcode.com/problems/deepest-leaves-sum/submissions/1274261758/

 

이진트리 검색에 대해서 개념을 잘 알고 있다면 어렵지 않은 문제이다.

 

하지만 나는 이진트리 알고리즘에 대해서 자세히 알지 못해서 조금 고심했던 문제였다.

 

이진트리 검색을 위해서는 기본적으로 dfs 로 구현해서 재귀적으로 계속 탐색해 나가야하는 것 같다.

 

node 가 null 일때, 재귀를 중단하고, 그게 아니라면 left 와 right 을 계속 탐색해 나가면서 value 값을 찾는 것이다.

 

이 문제에서는 이미 TreeNode 가 구현되어있기 때문에 따로 구현할 필요는 없이 탐색만 해나가면 되는 문제였다.

 

다른 사람들은 멋지게 문제를 풀지만 난 다소 둔탁하게 풀 수 밖에 없었다.

 

먼저 가장 낮은 depth 를 구하기 위해서 재귀함수로 deepest depth 를 구한다.

 

그 이후에 deepest depth 에 해당하는 node 가 나올때까지 탐색하여 해당 두 수를 더하여 리턴하는 방식이다.

 

코드로 보면 다음과 같다.

 

class Solution {

    private int deepDepth = 0;

    private int sum = 0;

    public int deepestLeavesSum(TreeNode root) {

        find(root, 0);

        findDeepDepthNode(root, 0);

        return sum;

    }

    void find(TreeNode root, int depth){

        if (root == null) {

            return;

        }

        deepDepth = Math.max(depth, deepDepth);

        find(root.left, depth+1);

        find(root.right, depth+1);

    }

    void findDeepDepthNode(TreeNode root, int depth) {

        if (root == null) {

            return;

        }

        if (depth == deepDepth) {

            sum+=root.val;

            return;

        }

        findDeepDepthNode(root.left, depth+1);

        findDeepDepthNode(root.right, depth+1);

    }

}