Portfolio

문제

1302. 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

풀이

은찬


/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var deepestLeavesSum = function(root) {
    let answer = 0;
    let maxDepth = 0;
    
    if(!root){
        return 0;
    }
    
    const bfs = (root) => {
        let maxDepth = 0;
        const queue = [];
        
        queue.push({
            node: root,
            depth: 1,
        });
    
        while(queue.length){
            const {node, depth} = queue[0];

            queue.splice(0, 1);

            if(maxDepth < depth){
                maxDepth = depth;
                answer = node.val;
            } else if(maxDepth === depth){
                answer += node.val;
            }

            if(node.left){
                queue.push({
                    node: node.left,
                    depth: depth + 1,
                });
            }

            if(node.right){
                queue.push({
                    node: node.right,
                    depth: depth + 1,
                });
            }
        }
    }
    
    const dfs = (node, depth) => {
        if(maxDepth < depth){
            maxDepth = depth;
            answer = node.val;
        } else if(maxDepth === depth){
            answer += node.val;
        }
        
        if(node.left){
            dfs(node.left, depth + 1);
        }
        
        if(node.right){
            dfs(node.right, depth + 1);
        }
    }
    
    dfs(root, 0);
    
    return answer;
};

효성


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

재영


const deepestLeavesSum = (root) => {
    let leaves = {};
    
    const dfs = (node, depth) => {
        if (node.left === null && node.right === null) {
            leaves[depth] = (leaves[depth] ?? []).concat([node.val])
        }
        
        if (node.left !== null) dfs(node.left, depth + 1);
        if (node.right !== null) dfs(node.right, depth + 1);
    }
    
    dfs(root, 0);
    
    return leaves[Object.keys(leaves).pop()].reduce((acc, cur) => acc + cur)
};