1302. Deepest Leaves Sum [Medium]

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

Deepest Leaves Sum - LeetCode

 

이진 트리가 주어졌을 때, 가장 깊은 서브트리가 아닌 가장 깊은 레벨의 합이다!

2번째 풀었는데 볼 때마다 헷갈리는거 같다.

3개의 풀이를 냈었다.

첫번째는 직접 푼거같고..

두번째는 답안지를 본거같다.

세번째는 첫번째랑 별 다를게 없다.

 

/**
 * 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:
    std::vector<int> vec_sum_;
    int max_deep_;
    void checkDeepestLeaves(TreeNode* root, int deep) {
        if (nullptr == root) {
            return;
        }

        if (nullptr == root->left && nullptr == root->right)
        {
            vec_sum_[deep] += root->val;
            max_deep_ = max_deep_ < deep ? deep : max_deep_;
            return;
        }

        if (nullptr != root->left) {
            checkDeepestLeaves(root->left, deep + 1);
        }
        if (nullptr != root->right) {
            checkDeepestLeaves(root->right, deep + 1);
        }
    }
    int deepestLeavesSum(TreeNode* root) {
        max_deep_ = 0;
        // 1 ~ 10^4개 이므로 16384 미만
        vec_sum_.resize(100, 0);
        checkDeepestLeaves(root, 0);
        return vec_sum_[max_deep_];
    }
};

 

/**
 * 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 res = 0, i;
        queue<TreeNode*> q;
        q.push(root);
        while (q.size()) {
            for (i = q.size() - 1, res = 0; i >= 0; --i) {
                TreeNode* node = q.front(); q.pop();
                res += node->val;
                if (node->right) q.push(node->right);
                if (node->left)  q.push(node->left);
            }
        }
        return res;
    }
};

 

 

/**
 * 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:
    void deepestLeavesSum(TreeNode* node, int deep) {
        if (node == nullptr) {
            return;
        }
        
        if (node->left || node->right)
        {
            deepestLeavesSum(node->left, deep + 1);
            deepestLeavesSum(node->right, deep + 1);
            return;
        }
        
        if (max_ < deep) {
            max_ = deep;
            val_ = node->val;
        }
        else if (max_ == deep) {
            val_ += node->val;
        }
    }
    int deepestLeavesSum(TreeNode* root) {   
        max_ = 0;
        val_ = 0;
        deepestLeavesSum(root, 1);
        return val_;
    }
private:
    int max_;
    int val_;
};