【二叉树, DFS】层数最深叶子节点的和

题目

1302. 层数最深叶子节点的和

---

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

示例 1：

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

示例 2：

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

提示：

• 树中节点数目在范围 [1, 10^4] 之间。
• 1 <= Node.val <= 100

解题

方法一：层序遍历

思路

使用二叉树的程序遍历，把每层的和都算出来最后返回最后一层的和即可。

代码

class Solution {
    private List<Integer> levelSums = new ArrayList<>();

    public int deepestLeavesSum(TreeNode root) {
        dfs(root, 0);
        return levelSums.get(levelSums.size() - 1);
    }

    private void dfs(TreeNode node, int level) {
        if (node == null) return;
        if (level == levelSums.size()) levelSums.add(node.val);
        else levelSums.set(level, levelSums.get(level) + node.val);
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
}

我们只需要最后一层的和，所以只用维护一个变量，遍历到哪层就维护哪层的和，最后剩下的一定是层数最深的和。

class Solution {
    int height = 0, levelSum;

    public int deepestLeavesSum(TreeNode root) {
        dfs(root, 0);
        return levelSum;
    }

    private void dfs(TreeNode node, int level) {
        if (node == null) return;
        if (level == height) levelSum += node.val;
        else if (level > height) {
            levelSum = node.val;
            ++height;
        }
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
}

// 这个lambda函数是用来关闭同步流的 和算法逻辑无关
int _ = []() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}();

class Solution {
    int height = 0, level_sum = 0;

public:
    int deepestLeavesSum(TreeNode* root) {
        dfs(root, 0);
        return level_sum;
    }

    void dfs(TreeNode* node, int level) {
        if (!node) return;
        if (level == height) level_sum += node->val;
        else if (level > height) {
            level_sum = node->val;
            ++height;
        }
        dfs(node->left, level + 1);
        dfs(node->right, level + 1);
    }
};