ToB企服应用市场:ToB评测及商务社交产业平台

标题: 【.Net力扣刷题】第1302题：层数最深叶子节点的和 [打印本页]

---

作者: 农妇山泉一亩田    时间: 2022-9-16 17:19
标题: 【.Net力扣刷题】第1302题：层数最深叶子节点的和
题目描述

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/deepest-leaves-sum/
给你一棵二叉树的根节点 root ，请你返回 层数最深的叶子节点的和 。
题目分析

本题需要遍历树找到层数最深的叶子节点，所以可以分为两种方式 深度优先搜索和广度优先搜索。
深度优先搜索（DFS）

通过递归寻找每个最深的节点，并将他们的数值进行累加。

1.     public int DeepestLeavesSum(TreeNode root)
2.     {
3.         int maxLenth = 0;
4.         int sum = 0;
5.         DFS(root, 1);
6.         return sum;
7.         void DFS(TreeNode node, int lenth)
8.         {
9.             if (node == null) return;
10.             if (lenth > maxLenth)
11.             {
12.                 maxLenth = lenth;
13.                 sum = node.val;
14.             }
15.             else if (lenth == maxLenth)
16.             {
17.                 sum += node.val;
18.             }
19.             DFS(node.left, lenth + 1);
20.             DFS(node.right, lenth + 1);
21.         }
22.     }

复制代码

广度优先搜索（BFS）

迭代读取每层的数值，则最后一次循环读取的必定是深度最高的节点，所以每次循环开始的时候将节点和置为0即可。

1.     public int DeepestLeavesSum2(TreeNode root)
2.     {
3.         int sum = 0;
4.         Queue<TreeNode> queue = new Queue<TreeNode>();
5.         queue.Enqueue(root);
6.         while (queue.Count > 0)
7.         {
8.             sum = 0;
9.             int size = queue.Count;
10.             for (int i = 0; i < size; i++)
11.             {
12.                 TreeNode node = queue.Dequeue();
13.                 sum += node.val;
14.                 if (node.left != null)
15.                 {
16.                     queue.Enqueue(node.left);
17.                 }
18.                 if (node.right != null)
19.                 {
20.                     queue.Enqueue(node.right);
21.                 }
22.             }
23.         }
24.         return sum;
25.     }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4