1022. Sum of Root To Leaf Binary Numbers

LeetCode easy оригинал: C# #backtracking #bit-manipulation #csharp #easy #graph #leetcode #recursion #search #tree #two-pointers

LeetCode Static

Вам дан корень двоичного дерева, в котором каждый узел имеет значение 0 или 1. Каждый путь от корня к листьям представляет собой двоичное число, начиная со старшего бита. Например, если путь 0 -> 1 -> 1 -> 0 -> 1, то в двоичном виде это может представлять 01101, что равно 13. Для всех листьев дерева рассмотрите числа, представленные путем от корня к этому листу. Верните сумму этих чисел. Тестовые примеры генерируются таким образом, чтобы ответ помещался в 32-битовое целое число.

Пример:

Input: root = [1,0,1,0,1,0,1]

Output: 22

C# решение

сопоставлено/оригинал

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
public class Solution {
    public int SumRootToLeaf(TreeNode root) {
        return Dfs(root, 0);
    }
    
    private int Dfs(TreeNode node, int currentValue) {
        if (node == null) return 0;
        currentValue = (currentValue << 1) | node.val;
        if (node.left == null && node.right == null) return currentValue;
        return Dfs(node.left, currentValue) + Dfs(node.right, currentValue);
    }
}

C++ решение

auto-draft, проверить перед отправкой

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}
class Solution {
public:
    public int SumRootToLeaf(TreeNode root) {
        return Dfs(root, 0);
    }
    
    private int Dfs(TreeNode node, int currentValue) {
        if (node == null) return 0;
        currentValue = (currentValue << 1) | node.val;
        if (node.left == null && node.right == null) return currentValue;
        return Dfs(node.left, currentValue) + Dfs(node.right, currentValue);
    }
}

Java решение

сопоставлено/оригинал

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public int sumRootToLeaf(TreeNode root) {
        return dfs(root, 0);
    }
    
    private int dfs(TreeNode node, int currentValue) {
        if (node == null) return 0;
        currentValue = (currentValue << 1) | node.val;
        if (node.left == null && node.right == null) return currentValue;
        return dfs(node.left, currentValue) + dfs(node.right, currentValue);
    }
}

JavaScript решение

сопоставлено/оригинал

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    sumRootToLeaf(root) {
        const dfs = (node, currentValue) => {
            if (!node) return 0;
            currentValue = (currentValue << 1) | node.val;
            if (!node.left && !node.right) return currentValue;
            return dfs(node.left, currentValue) + dfs(node.right, currentValue);
        };
        
        return dfs(root, 0);
    }
}

Go решение

сопоставлено/оригинал

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func sumRootToLeaf(root *TreeNode) int {
    var dfs func(*TreeNode, int) int
    dfs = func(node *TreeNode, current_value int) int {
        if node == nil {
            return 0
        }
        current_value = (current_value << 1) | node.Val
        if node.Left == nil && node.Right == nil {
            return current_value
        }
        return dfs(node.Left, current_value) + dfs(node.Right, current_value)
    }
    
    return dfs(root, 0)
}

Algorithm

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

Используйте функцию DFS (поиск в глубину) для обхода дерева, начиная от корня. Передавайте текущее значение числа по пути как параметр.

2⃣Анализ текущего узла:

Если узел является листом (не имеет потомков), добавьте текущее значение числа к общей сумме.

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

3⃣Возврат результата:

После завершения обхода верните общую сумму чисел, представленных путями от корня к листьям.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.