1302. Deepest Leaves Sum

其實我覺得這題好像用bfs更好, 可以直接紀錄到最後一層

如果用dfs, 就是給一個hashtable, 然後針對各層的深度進行總和, 最後抓出最深那層的sum

/**
 * 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 dfs(TreeNode *root, unordered_map<int, int> &depth_sum, int cur_depth, int cur){
        if(!root) return;
        depth_sum[cur_depth] += root->val;
        if(!root->right && !root->left ){
            return;
        }
        
        if(root->right)
            dfs(root->right, depth_sum, cur_depth + 1, cur);
        if(root->left){
            dfs(root->left, depth_sum, cur_depth + 1, cur);
        }
    }
    int deepestLeavesSum(TreeNode* root) {
        int res = 0;
        unordered_map<int, int> depth_sum;
        dfs(root, depth_sum, 0, 0);
        int depth = -1;
        for(auto i: depth_sum){
            if(i.first >depth){
                depth = i.first;
                res = i.second;
            }
        }
        
        return res;
    }
};