【.Net力扣刷题】第1302题:层数最深叶子节点的和

  • 【.Net力扣刷题】第1302题:层数最深叶子节点的和已关闭评论
  • 27 次浏览
  • A+
所属分类:.NET技术
摘要

来源:力扣(LeetCode)链接:https://leetcode.cn/problems/deepest-leaves-sum/给你一棵二叉树的根节点 root ,请你返回 层数最深的叶子节点的和 。


题目描述

来源:力扣(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;     }