【.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;     }