1302题

和104题一样
方法一：宽度遍历（BFS）
遇到问题：1、未及时弹出队列数据导致运行超时
2、可以使用官方给的定义方式
3、尽量使用emplace代替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:
    int deepestLeavesSum(TreeNode* root) {
        if(root==NULL){
            return 0;
        }
        int result=0;
        int maxdep=-1;
        queue<pair<TreeNode*,int>>q;
        q.emplace(root,0);
        while(!q.empty()){
            TreeNode* head=q.front().first;
            int depth = q.front().second;
            q.pop();
            if(depth>maxdep){
                result=head->val;
                maxdep=depth;
            }
            else if(depth==maxdep){
                result+=head->val;
            }
            if(head->left){
                q.emplace(head->left,depth+1);
            }
            if(head->right){
                q.emplace(head->right,depth+1);
            }
        }
        return result;
    }
};

方法二：深度遍历递归(DFS)，前序遍历，使节点记住自己所在层若为最深层节点则加入到result结果中

class Solution {
private:
    int result = 0;
    int maxdep=-1;
public:
void DFS(TreeNode*root,int depth){
        if(root==NULL){
            return;
        }
        if(depth>maxdep){
            maxdep=depth;
            result=root->val;
        }
        else if(depth==maxdep){
            result+=root->val;
        }
        DFS(root->left,depth+1);
        DFS(root->right,depth+1);
    }
    int deepestLeavesSum(TreeNode* root) {
        DFS(root,0);
        return result;
    }
};