1302. Deepest Leaves Sum

Leetcode link

解题思路

这道题可以用队列与递归两种方法来写，因为思路很简单我用 C++ 实现了队列；用 js 实现递归

队列的话记得把每一行的最后一个元素后面插入一个空指针判别一行的结束

递归的话需要额外的一个变量来记录最深的层数，只需要记录最深那一层的加总就好

C++——队列

class Solution {
public:
    int deepestLeavesSum(TreeNode* root) {
        queue<TreeNode*> pq;
        int sum = 0;
        pq.push(root);
        pq.push(nullptr);
        while(pq.size() > 1) {
            TreeNode* node = pq.front();
            pq.pop();
            if(node == nullptr) {
                pq.push(nullptr);
                sum = 0;
                continue;
            }
            sum+=node->val;
            if(node->left) {
                pq.push(node->left);
            }
            if(node->right) {
                pq.push(node->right);
            }
        }
        return sum;
    }
};

Javascript——递归

var deepestLeavesSum = function(root) {
    let deepestLevel = 1;
    let sum = 0;

    let dfs = (node, level) => {
        if(!node) {
            return;
        }

        dfs(node.left, level+1);
        if(level > deepestLevel) {
            deepestLevel = level;
            sum = node.val;
        } else if(level == deepestLevel) {
            sum += node.val;
        }
        dfs(node.right, level+1);
    }

    dfs(root, 1);
    return sum;
};