LeetCode 솔루션

[5/15] 1302. Deepest Leaves Sum

mingki 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.05.14 20:14

7,642 조회
4 댓글
0 추천
0 비추천
목록 게시글 쓰기

[LeetCode 시즌 3] 2022년 5월 15일 문제입니다.

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

1302. Deepest Leaves Sum

Medium

256778Add to ListShare

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

#LeetCode, #Apple, #Amazon, #Microsoft, #Google, #Tree, #Depth-First Search(DFS), #Breadth-First Search(BFS), #Binary Search

링크

https://leetcode.com/problems/deepest-leaves-sum/ 2110 회 연결

익명
작성일 2022.05.14 20:15

C++
Runtime: 110 ms, faster than 80.06% of C++ online submissions for Deepest Leaves Sum.
Memory Usage: 59.8 MB, less than 76.50% of C++ online submissions for Deepest Leaves Sum.

class Solution {
    map<int, int> m;
    
public:
    int deepestLeavesSum(TreeNode* root, int h = 1) {
        if (root) {
            m[h] += root->val;
            deepestLeavesSum(root->left, h + 1);
            deepestLeavesSum(root->right, h + 1);
        }
        return m.rbegin()->second;
    }
};

익명
작성일 2022.05.14 20:33

class Solution {
public:
    int deepestLeavesSum(TreeNode* root) {
        int ret;
        for(vector<TreeNode*> q(1,root), next; !q.empty(); q = move(next)) {
            ret = 0;
            for(auto node : q) {
                ret += node->val;
                if (node->left) next.emplace_back(node->left);
                if (node->right) next.emplace_back(node->right);
            }
        }
        return ret;
    }
};

익명
작성일 2022.05.14 21:13

class Solution:
    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        que = []
        que.append(root)
        temp_sum = 0
        while que:
            size = len(que)
            temp_sum = 0
            for i in range(size):
                front = que.pop(0)
                temp_sum += front.val
                if front.left:
                    que.append(front.left)
                if front.right:
                    que.append(front.right)
        return temp_sum

익명
작성일 2022.05.15 12:03

BFS - Queue 활용

# bfs

from collections import deque
class Solution:
    def deepestLeavesSum(self, root: Optional[TreeNode]) -> int:
        
        if not root:
            return 0
        
        queue = deque()
        queue.append(root)
        
        while queue:
            cur_sum = 0
            cur_size = len(queue)
            
            for _ in range(cur_size):
                node = queue.popleft()
                cur_sum += node.val

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

        return cur_sum