Задача: 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) и подсчитайте сумму всех путей от корня к листьям.

😎 Решение:

class Solution {
    function pathSum($nums) {
        $tree = [];
        
        foreach ($nums as $num) {
            $depth = intdiv($num, 100);
            $pos = intdiv($num, 10) % 10;
            $val = $num % 10;
            $tree[$depth * 10 + $pos] = $val;
        }
        
        return $this->dfs($tree, 1, 1, 0);
    }
    
    private function dfs($tree, $depth, $pos, $currentSum) {
        $key = $depth * 10 + $pos;
        if (!isset($tree[$key])) {
            return 0;
        }
        $currentSum += $tree[$key];
        $leftChild = ($depth + 1) * 10 + 2 * $pos - 1;
        $rightChild = ($depth + 1) * 10 + 2 * $pos;
        if (!isset($tree[$leftChild]) && !isset($tree[$rightChild])) {
            return $currentSum;
        }
        return $this->dfs($tree, $depth + 1, 2 * $pos - 1, $currentSum) + $this->dfs($tree, $depth + 1, 2 * $pos, $currentSum);
    }
}

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