题目描述
来源:力扣(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;
}
标签:node,queue,1302,int,sum,力扣,lenth,Net,节点
From: https://www.cnblogs.com/xqrdbky/p/16596542.html