[Leetcode][Java]1302 Deepest Leaves Sum ( 가장 끝의 잎들의 합)

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

 

binary tree의 root 값이 주어진 상황에서, 가장 끝에 있는 잎들의 합을 반환해라.

---

dfs를 이용해서 답을 구해 보자. 

dfs를 타고 갈 때마다 level의 값을 하나씩 더해주어 해당 노드의 level을 파악하고

해당 level이 maxLevel보다 큰 경우에는 maxLevel값으로 세팅해 주면서 해결해 나갈 수 있을 것으로 보인다. 

    private void dfs(TreeNode node, int level) {

        if (level  > maxLevel) {
            sum = 0;
            maxLevel = level;
        }

        if (level == maxLevel) {
            sum += node.val;
        }

        if (node.right != null) {
            dfs(node.right, level+1);            
        }

        if (node.left != null) {
            dfs(node.left, level+1);
        }
    }

 

해당 메서드를 호출하는 내역을 보자

sum, maxLevel은 전역 변수를 사용하였다.

    int sum = 0;
    int maxLevel = 0;

    public int deepestLeavesSum(TreeNode root) {
        int level = 0;

        if (root != null) {
            dfs (root, level);
        }

        return sum;    
    }

 

문제 출처 

leetcode.com/problems/deepest-leaves-sum/

Deepest Leaves Sum - LeetCode