Задача: 666. Path Sum IV
Сложность: medium

Если глубина дерева меньше 5, то это дерево можно представить в виде массива трехзначных чисел. Для каждого числа в этом массиве:

Сотни представляют глубину d этого узла, где 1 <= d <= 4.
Десятки представляют позицию p этого узла на уровне, которому он принадлежит, где 1 <= p <= 8. Позиция соответствует позиции в полном бинарном дереве.
Единицы представляют значение v этого узла, где 0 <= v <= 9.
Дан массив возрастающих трехзначных чисел nums, представляющих бинарное дерево с глубиной меньше 5. Верните сумму всех путей от корня к листьям.

Гарантируется, что данный массив представляет собой валидное связанное бинарное дерево.

Пример:

Input: nums = [113,215,221]
Output: 12
Explanation: The tree that the list represents is shown.
The path sum is (3 + 5) + (3 + 1) = 12.

👨‍💻 Алгоритм:

1⃣Создание структуры дерева:
Пройдите по массиву nums и для каждого элемента создайте узел дерева.
Сохраните узлы в словаре для удобного доступа по их позиции.

2⃣Связывание узлов:
Пройдите по массиву и свяжите узлы друг с другом, исходя из их позиции и глубины.
Найдите левого и правого ребенка для каждого узла и установите соответствующие связи.

3⃣Подсчет суммы путей:
Выполните обход дерева (например, используя DFS) и подсчитайте сумму всех путей от корня к листьям.

😎 Решение:

public class Solution {
    public int PathSum(int[] nums) {
        var tree = new Dictionary<int, int>();
        
        foreach (int num in nums) {
            int depth = num / 100;
            int pos = (num / 10) % 10;
            int val = num % 10;
            tree[depth * 10 + pos] = val;
        }
        
        return Dfs(tree, 1, 1, 0);
    }
    
    private int Dfs(Dictionary<int, int> tree, int depth, int pos, int currentSum) {
        int key = depth * 10 + pos;
        if (!tree.ContainsKey(key)) {
            return 0;
        }
        currentSum += tree[key];
        int leftChild = (depth + 1) * 10 + 2 * pos - 1;
        int rightChild = (depth + 1) * 10 + 2 * pos;
        if (!tree.ContainsKey(leftChild) && !tree.ContainsKey(rightChild)) {
            return currentSum;
        }
        return Dfs(tree, depth + 1, 2 * pos - 1, currentSum) + Dfs(tree, depth + 1, 2 * pos, currentSum);
    }
}

Ставь 👍 и забирай 📚 Базу знаний