[LeetCode C++] 1302. Deepest Leaves Sum

⭐️ 난이도

Medium

---

⭐️ 문제

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

Deepest Leaves Sum - LeetCode

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

이진 트리(binary tree)의 root가 주어진다. 이 때, 깊이(depth)가 가장 같은 leave들의 합을 구하라.

 

---

⭐️ Follow-up

X

 

---

⭐️ Idea flow

 

 

 

 

 

 

 

 

 

root = [1,2,3,4,5,null,6,7,null,null,null,null,8]

 

먼저 문제 이해를 위해 예시를 살펴보자.

 

이진 트리가 위와 같을 때, root가 [1,2,3,4,5,null,6,7,null,null,null,null,8]와 같은 형식으로 주어진다.

주어진 순서를 살펴보면 level 별로 순회한 것을 알 수 있다.

 

위의 이진 트리에서 deepest leaves는 depth가 4인 노드인 7와 8이다.

따라서 각 노드의 depth를 확인할 필요가 있다. depth 0에서부터 차례로 순회를 하면 같은 depth인 노드들을 알 수 있다.

여기서 BFS를 이용하면 depth, 즉 level 순회가 가능할 것이다.

 

알고리즘은 다음과 같다.

1) root에서부터 BFS(queue)를 이용하여 level 순회를 한다.

2) queue에 push할 때 level을 하나 올려주고, max_level을 갱신해준다.

   동시에 multimap[level]에 해당 노드의 값을 value값으로 넣어준다.

3) BFS가 완료되면, multimap[level]에 해당하는 value값들을 모두 더해서 반환한다.

 

 

---

⭐️ Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:    
    int deepestLeavesSum(TreeNode* root) {
        int max_level = 0, result = 0;
        multimap<int, int> hashmap;
        queue<pair<TreeNode*, int>> q;
        q.push({root, 0});


        while(!q.empty()){
            TreeNode* cur = q.front().first; // 현재 노드
            int cur_level = q.front().second; // 현재 노드의 레벨
            q.pop();

            max_level = max(max_level, cur_level);
            hashmap.insert({cur_level, cur->val});

            if(cur->left != nullptr){
                q.push({cur->left, cur_level + 1});
            }
            if(cur->right != nullptr){
                q.push({cur->right, cur_level + 1});
            }
        }

        for(auto iter = hashmap.lower_bound(max_level); iter != hashmap.upper_bound(max_level); iter++){
            result += iter->second;
        }
        return result;
    }
};

 

 

---

⭐️ Feedback

1. DFS

 

level 순회에 DFS는 적절하지 않을 것이라고 생각했는데, DFS도 꽤나 좋은 방법이었다.

먼저 DFS는 재귀를 바탕으로 진행되기 때문에,

현재까지의 depth의 최대 값을 저장할 변수 max_level과, 노드의 합을 저장할 변수 sum을 선언한다.

root를 기준으로 depth = 0으로 설정한다.

 

만약 해당 노드가 자식 노드가 없는 leaf node라면 현재의 depth를 확인한다.

1) 만일 최대 depth와 현재 depth가 같다면 sum에 현재 노드의 값을 더한다.

2) 만일 최대 depth보다 현재 depth가 더 깊다면, sum을 현재 노드의 값으로 설정하고, 최대 depth를 갱신한다.

3) 왼쪽 자식과 오른쪽 자식으로 DFS를 진행한다.

   이 때, depth 매개변수를 1 증가시켜 전달한다.

 

 

[전체 코드 보기]

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int max_level = 0, sum = 0;
    
    // Using DFS
    int deepestLeavesSum(TreeNode* root, int depth = 0) {
        if(!root)   return 0;
        
        // leaf node
        if(!root->left && !root->right){
            if(max_level == depth){
                sum += root->val;
            }
            else if(max_level < depth){
                sum = root->val;
                max_level = depth;
            }
        }
        deepestLeavesSum(root->left, depth + 1);
        deepestLeavesSum(root->right, depth + 1);
        return sum;
    }
};

 

 

2. BFS

 

내가 풀었던 방식과 비슷하지만 노드의 값을 따로 저장하지 않아 메모리를 더 절약할 수 있는 방법이 있었다.

바로 queue의 size를 이용하는 방식이다.

이렇게 하면 같은 level(depth)에 있는 노드들만 방문이 가능하다.

 

for문을 이용해 queue의 size 만큼만 돌면서 값을 더하고, 왼쪽 자식 or 오른쪽 자식이 있을 때 해당 노드를 queue에 push해서 다음 방문을 진행하도록 한다.

 

 

 

[전체 코드 보기]

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // using BFS
    int deepestLeavesSum(TreeNode* root) {
        if(root == nullptr) return 0;
        
        queue<TreeNode*> q;
        int sum = 0;
        q.push(root);
        
        while(!q.empty()){
            int q_size = q.size();
            sum = 0;
            
            for(int i = 0; i < q_size; i++){
                TreeNode* cur = q.front();
                q.pop();
                sum += cur->val;
                if(cur->left)   q.push(cur->left);
                if(cur->right)  q.push(cur->right);
            }
        }
        return sum;
    }
};

 

## unordered_multimap에서는 lower_bound와 upper_bound를 사용하지 못한다.

    대신 find를 사용하면 된다. 왤까?