【.Net力扣刷题】第1302题:层数最深叶子节点的和
2023-03-31 10:59:28 时间
题目描述
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/deepest-leaves-sum/
给你一棵二叉树的根节点 root ,请你返回 层数最深的叶子节点的和 。
题目分析
本题需要遍历树找到层数最深的叶子节点,所以可以分为两种方式 深度优先搜索和广度优先搜索。
深度优先搜索(DFS)
通过递归寻找每个最深的节点,并将他们的数值进行累加。
public int DeepestLeavesSum(TreeNode root)
{
int maxLenth = 0;
int sum = 0;
DFS(root, 1);
return sum;
void DFS(TreeNode node, int lenth)
{
if (node == null) return;
if (lenth > maxLenth)
{
maxLenth = lenth;
sum = node.val;
}
else if (lenth == maxLenth)
{
sum += node.val;
}
DFS(node.left, lenth + 1);
DFS(node.right, lenth + 1);
}
}
广度优先搜索(BFS)
迭代读取每层的数值,则最后一次循环读取的必定是深度最高的节点,所以每次循环开始的时候将节点和置为0即可。
public int DeepestLeavesSum2(TreeNode root)
{
int sum = 0;
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count > 0)
{
sum = 0;
int size = queue.Count;
for (int i = 0; i < size; i++)
{
TreeNode node = queue.Dequeue();
sum += node.val;
if (node.left != null)
{
queue.Enqueue(node.left);
}
if (node.right != null)
{
queue.Enqueue(node.right);
}
}
}
return sum;
}
相关文章
- 划入 .NET 6 版本目标,微软鼓励开发人员信任第三方库
- 关于.NET生态,你了解多少?
- Steeltoe:简化.NET云微服务的构建
- 全面了解微软.NET 5,2021年更好迈向.NET 6
- 光棍节微软发布dotNET 5.0正式版本,新功能尝鲜
- 阻塞 、非阻塞;同步、异步
- 模型驱动设计的构造块(下)——DDD
- 模型驱动设计的构造块(上)——DDD
- ASP.NET Core 应用程序状态
- Asp.net core 简单介绍
- ASP.NET Core 多环境
- ASP.NET Core 依赖注入(DI)
- ASP.NET Core 配置文件
- ASP.NET Core 静态文件
- 自定义ASP.NET Core日志中间件
- dotnet体系结构
- Clojure世界:文件IO
- Apache MINA (1) 简介
- [WPF] 制作一个彩虹按钮
- DDD领域驱动设计 — 贫血模型与充血模型