侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-08-17 / 0 评论 / 0 点赞 / 41 阅读 / 423 字 / 正在检测是否收录...

题目

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);
    }
};
0

评论区