【.Net力扣刷题】第1302题：层数最深叶子节点的和
题目描述来源：力扣（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;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]