“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
            // Add the results
            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

breadth-first

  • 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