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

Topic link

404. Sum of Left Leaves – LeetCode (leetcode-cn.com)

Topic describes

Computes the sum of all left leaves of a given binary tree.

The test case

Example 1:

3 / \ 9 20 / \ 15 7 In this binary tree, there are two left leaves, 9 and 15, so return 24Copy the code

Subject analysis

The problem is very simple. All we need to do is find the sum of all the left leaf nodes on a binary tree, the nodes marked in the figure above

We need to first locate the characteristics of the nodes we are asked to sum:

  1. This type of node has no children
  2. Such a node is the left child of its parent

Therefore, the problem obviously cannot be solved by focusing on the left leaf node. We need to determine the parent node of this node, as shown in the following figure

When you convert the condition, it will be, this parent will have a left child, and this left child will not have any children under it. When we find such a node, we can directly add up the value of the left child node of the node

The approximate function implementation is to traverse a node, judge that the left child node is not empty and the left child node is a leaf node when it is not empty, add the value of the left child node of this node, and then continue to traverse the left and right child nodes of this node in a recursive mode

Code implementation

var sumOfLeftLeaves = function(root) {
    let sum = 0;
    trave(root);
    return sum;

    function trave(root) {
        if (root == null) return;
        trave(root.left);
        trave(root.right);
        if(root.left ! =null && root.left.left == null && root.left.right == null) { sum += root.left.val; }}};Copy the code

When we figure out the structure of a binary tree and how recursion works, we can solve this problem very easily