###### tags: `LeetCode` `Tree` `Recursion` `Medium` `Queue`
# LeetCode #1302 [Deepest Leaves Sum](https://leetcode.com/problems/deepest-leaves-sum/)
### (Medium)
給你一棵二元樹的根節點 root ，請你返回層數最深的葉子節點的和 。

---
方法1 :
先將每一節點插到他所屬層數的數組內, 再計算數組最後一組元素的和。

class Solution {
public:
    vector<vector<int>> nodes;
    int deepestLeavesSum(TreeNode* root) {
        if(root){
            nodes.emplace_back();
            nodes[0].push_back(root->val);
            helper(root->left, 1);
            helper(root->right, 1);
            int ans=0;
            for(auto i:nodes[nodes.size()-1])ans+=i;
            return ans;
        }
        return 0;
    }
    void helper(TreeNode* root, int level){
        if(root){
            if(level==nodes.size())nodes.emplace_back();
            helper(root->left, level+1);
            helper(root->right, level+1);
            nodes[level].push_back(root->val);
        }
    }
};

---
方法2 :
使用佇列插入每層的節點, 並計算每層節點的數字合並更新至ans中(也就是下一層的和會蓋掉上一層的)。

當佇列為空時, 就是佇列釋放完最後一層的節點並計算該層節點和並更新至ans中, 此時回傳ans即為答案。

class Solution {
public:
    int deepestLeavesSum(TreeNode* root) {
        queue<TreeNode*> q;
        int ans=0,i;
        q.push(root);
        while(q.size()){
            for(i=q.size()-1, ans=0;i>=0;i--){
                TreeNode* tmp=q.front();q.pop();
                ans+=tmp->val;
                if(tmp->right)q.push(tmp->right);
                if(tmp->left)q.push(tmp->left);
            }
        }
        return ans;
    }
};