[LeetCode刷題筆記] 1302 – Deepest Leaves Sum

題目描述：

Given the root of a binary tree, return the sum of values of its deepest leaves.

Example 1:

Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
Output: 15

Example 2:

Input: root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
Output: 19

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• 1 <= Node.val <= 100

一刷題解（兩次DFS）：

這題給我們一個二叉樹，然後需要我們得出這個二叉樹中，最深的葉節點的值的總和。最直接，也是作者給出的提示思路就是對樹進行兩次遍歷。第一次遍歷得出樹的深度；第二次遍歷再根據這個深度的基礎上，找到最深的節點，並將它們的值加起來。

public class Solution {    
    public int DeepestLeavesSum(TreeNode root) {
        //第一次DFS得出最大深度
        int depth = DepthFinder(root);
        //第二次DFS根據深度找到最深的葉節點並計算總和
        int sum = SumFinder(root, depth);        
        return sum;
    }
    //深度
    int DepthFinder(TreeNode node)
    {
        if(node == null) { return 0; }
        int depth = 1;
        int leftDepth = DepthFinder(node.left);
        int rightDepth = DepthFinder(node.right);
        
        depth = depth + Math.Max(leftDepth, rightDepth);
        return depth;
    }
    //得到最深節點的值
    int SumFinder(TreeNode node, int depth)
    {
        if(node == null) { return 0; }
        if(depth == 1 && node != null)
        {
            return node.val;
        }
        
        return SumFinder(node.left, depth - 1) + SumFinder(node.right, depth - 1);
    }
}