404. Sum of Left Leaves

leetcode easy

#csharp#easy#graph#leetcode#recursion#tree#two-pointers

Task

Если задан корень бинарного дерева, верните сумму всех левых листьев. Лист - это узел, не имеющий детей. Левый лист - это лист, который является левым ребенком другого узла.

Пример:

Input: root = [3,9,20,null,null,15,7]

Output: 24

C# solution

matched/original

public class Solution {
    public int SumOfLeftLeaves(TreeNode root) {
        return Dfs(root, false);
    }
    
    private int Dfs(TreeNode node, bool isLeft) {
        if (node == null) return 0;
        if (node.left == null && node.right == null) return isLeft ? node.val : 0;
        return Dfs(node.left, true) + Dfs(node.right, false);
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int SumOfLeftLeaves(TreeNode root) {
        return Dfs(root, false);
    }
    
    private int Dfs(TreeNode node, bool isLeft) {
        if (node == null) return 0;
        if (node.left == null && node.right == null) return isLeft ? node.val : 0;
        return Dfs(node.left, true) + Dfs(node.right, false);
    }
}

Java solution

matched/original

public class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        return dfs(root, false);
    }
    
    private int dfs(TreeNode node, boolean isLeft) {
        if (node == null) return 0;
        if (node.left == null && node.right == null) return isLeft ? node.val : 0;
        return dfs(node.left, true) + dfs(node.right, false);
    }
}

JavaScript solution

matched/original

class Solution {
    sumOfLeftLeaves(root) {
        return this.dfs(root, false);
    }
    
    dfs(node, isLeft) {
        if (!node) return 0;
        if (!node.left && !node.right) return isLeft ? node.val : 0;
        return this.dfs(node.left, true) + this.dfs(node.right, false);
    }
}

Python solution

matched/original

class Solution:
    def sumOfLeftLeaves(self, root: TreeNode) -> int:
        def dfs(node, is_left):
            if not node:
                return 0
            if not node.left and not node.right:
                return node.val if is_left else 0
            return dfs(node.left, True) + dfs(node.right, False)
        
        return dfs(root, False)

Go solution

matched/original

func sumOfLeftLeaves(root *TreeNode) int {
    return dfs(root, false)
}

func dfs(node *TreeNode, isLeft bool) int {
    if node == nil {
        return 0
    }
    if node.Left == nil && node.Right == nil {
        if isLeft {
            return node.Val
        }
        return 0
    }
    return dfs(node.Left, true) + dfs(node.Right, false)
}

Explanation

Algorithm

Рекурсивный обход дерева

Обходите дерево с помощью рекурсивной функции, которая принимает текущий узел и флаг, указывающий, является ли узел левым ребенком.

Проверка листьев

Если текущий узел является листом и флаг указывает, что это левый ребенок, добавьте значение узла к сумме.

Рекурсивный вызов для детей

Рекурсивно вызовите функцию для левого и правого детей текущего узла, передавая соответствующий флаг.

😎