99클럽 코테 스터디 : 깊이/너비 우선탐색(DFS/BFS) - Deepest leaves sum

이것두 TIL은 아니지만,,

그래도 문제푼거 기록은 해둬야할것같으니까!!

---

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

문제는 간단하다. 이진트리가 주어지고, 가장 depth가 깊은 leave들의 sum을 구하면 되는 문제이다.

처음에는 가장 depth가 깊은 path의 노드들의 합으로 생각해서 잘못풀었다..ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

문제자체는 쉽게풀었는데 여러모로 효율이 안좋았어서 이것저것 찾아봤다.

---

 

쉽게 통과는 했는데 시간이 오래걸린다.

/**
 * 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:

    // test[0] : val
    // test[1] : level
    void DFS(TreeNode* nownode, vector<int> test, vector<vector<int>> &result){
        test[0] = nownode->val;
        test[1] += 1;
        if(nownode->left == NULL && nownode->right == NULL){
            result.push_back(test);
            return;
        }
        if(nownode->left != NULL){
            DFS(nownode->left, test, result);
        }
        if(nownode->right != NULL){
            DFS(nownode->right, test, result);
        }
        
    }

    int deepestLeavesSum(TreeNode* root) {
        
        vector<vector<int>> result;
        vector<int> test = {0,0};

        DFS(root, test, result);

        int maxlevel = 0;
        int maxsum = 0;
        for(int i = 0; i<result.size(); i++){
            if(result[i][1] > maxlevel){
                maxlevel = result[i][1];
            }
        }

         for(int i = 0; i<result.size(); i++){
            if(result[i][1] == maxlevel){
                maxsum += result[i][0];
            }
        }

        //cout << maxlevel << endl;
        return maxsum;
    }
};

최적화가 필요할것같다.

 

---

혼자 생각하다가 답이 안나서 solution에 있는 다른사람 풀이를 참고했다.

/**
 * 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:

    // test[0] : val
    // test[1] : level
    void DFS(TreeNode* nownode, int level, int &sum, int &depth){
        
        //cout << "nowlevel : "<<nowlevel<<""<<endl;
        if(nownode == NULL){
            //cout << "null"<<endl;
            return;
        }
        if(level == depth){
            //cout << "level == depth, nownode->val : " << nownode->val<<endl;
            sum += nownode->val;
        }else if(level > depth){
            //cout << "level > depth, nownode->val : " << nownode->val<<endl;
            sum = nownode->val;
            depth = level;
        }
        DFS(nownode->left,level+1, sum, depth );
        DFS(nownode->right, level+1, sum, depth);
        
    }

    int deepestLeavesSum(TreeNode* root) {
        
        int sum = 0;
        int depth = 1;

        DFS(root, 1, sum, depth);

        

        //cout << maxlevel << endl;
        return sum;
    }
};

 

내 코드는 일단 leaf노드를 전부 찾고

leaf 중 레벨이 가장 높은값을 찾고

그 레벨에 해당되는 leaf들의 값을 더했다.

 

참고한 코드는 애초에 DFS할 때 sum을 해준다!!

즉 지금 level이 최대level이면 sum에 더해주는데,

지금level이 기존의 최대level보다 깊어졌다?? 그러면 최대level을 업데이트하고 sum을 다시 시작한다!!

나는 쓸데없는 동작이 많았는데 이런식으로 생각했어야 했다....