题目描述

给你一棵二叉树，请你返回层数最深的叶子节点的和。

样例

输入：root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
输出：15

算法1

递归遍历 额外记录下层级 然后叶子放入一个容器 以层级排序 输出

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<pair<int,int>> leaf;
    void dfs(TreeNode* root,int level){
         if(root == NULL) return ;
        if(root->left == NULL && root->right == NULL) {
            leaf.push_back({level,root->val});
        }

        dfs(root->left,level+1);
        dfs(root->right,level+1);
    }

    int deepestLeavesSum(TreeNode* root) {
        dfs(root,0);   
        sort(leaf.begin(),leaf.end());
        int retsum =0;
        int levellimit = leaf.back().first;
        for(int i= leaf.size()-1; i >=0 ;i--){
            if(leaf[i].first == levellimit){
                retsum += leaf[i].second;
            }else{
                break;
            }
        }
        return retsum;
    }
};

我的leetcode视频题解空间