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