[트리] 1302. Deepest Leaves Sum (가장 깊은 잎들의 합을 구하기)

Given 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
 

Constraints:

The number of nodes in the tree is between 1 and 10^4.
The value of nodes is between 1 and 100.

var deepestLeavesSum = function(root) {
    let maxDepth = 0;
    const arr = [];
    
    const dfs = (root, curDepth) => {
        if(!root) return;
        if(!root.left && !root.right) {
            arr.push({
                depth: curDepth,
                value: root.val
            });
            maxDepth = Math.max(maxDepth, curDepth);
        }
        
        dfs(root.left, curDepth + 1);
        dfs(root.right, curDepth + 1);
    }
        
    dfs(root, 0);
    
    const result = arr.reduce((acc, cur) => {
        return cur.depth === maxDepth ? acc + cur.value : acc + 0;
    }, 0);
    
    return result;
};

dfs로 트리를 순회하면서 현재 깊이값을 기록한다. 현재 노드가 잎일 경우 현재 노드의 깊이와 value를 배열에 저장해둔다. 그리고 최대 깊이 또한 기록해둔다.

 

모든 트리를 순회하고 나서 아까 저장해둔 배열을 한번더 순회하면서 최대 깊이와 똑같은 깊이를 가진 엘리먼트를 찾아서 그 엘리먼트의 value를 더해서 리턴하면 된다.(그러면 트리에 있는 모든 최대 깊이 노드들의 value를 더해줄수있다.)