“This is the first day of my participation in the First Challenge 2022. For details: First Challenge 2022”

## Title: Sum of the deepest leaf nodes

Given the root node of a binary tree, return the sum of the deepest leaf nodes.

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

### parsing

1. You have to go to the last level and add the values of the last level
2. Depth first or breadth first

### code

#### Depth first

• First: summation, we need a sum of variables r
• To record whether a node depth is the last layer, a maxDepth maximum depth variable 0 is required
• Because it is depth-first, when we traverse down each time, when the depth is greater than the maximum depth of our current traversal, the value of maxDepth needs to be updated, and our and r needs to be reset to the value of the current node. When the single front section depth is equal to the current maximum depth, Represents the maximum depth at which the current node is located, and our and r need to add the value of the current node
• Since the root node depth was 1 when the traversal began, the depth passed to the current node should be 1
• To sum up: we can use recursion, passing in the current node and the depth of the current node
``````function deepestLeavesSum(root) {
// Define the result and
let r = 0
// Define a specified maximum depth
let maxDepth = 0
function dfs(node, depth) {
// Return if the node is empty
if (node === null) return

if (maxDepth < depth) {
// When it comes to a deeper level
/ / update the maxDepth
maxDepth = depth
// reset the value of r
r = node.val
} else if (maxDepth === depth) {
// When the depth of the current node is at the same level as the maximum depth
r += node.val
}
// When maxDepth > depth, just continue traversing

// Recurse left and right nodes
dfs(node.left, depth + 1)
dfs(node.right, depth + 1)}// Root node and depth pass in
dfs(root, 1)

return r
}
Copy the code``````

• Add the sum using sequential traversal to the last layer node
• My steps are: sequence traversal and save the last layer of nodes, then reduce the sum
``````// First define the sequence traversal to find the deepest node array
function findMaxDepNodes(root) {
if (root === null) return []
const stack = [root]
const maxDepNodes = []
while(stack.length) {
// Stores the nodes of the next layer
const temp = []
for (let i = 0; i < stack.length; i++) {
const node = stack[i]

if (node.left) temp.push(node.left)
if (node.right) temp.push(node.right)
}

// If the next layer has no nodes, it is the last layer
if (temp.length === 0) {
maxDepNodes = stack
}

stack = temp
}

return maxDepthNodes
}

function deepestLeavesSum(root) {
const rnodes = findMaxDepNodes(root)
return rnodes.reduce((a, b) = > a + b.val, 0)}Copy the code``````

## conclusion

• It’s a great practice of depth first breadth first
• I’m hitting the easy questions again