root двоичного дерева с целыми значениями в вершинах.
Поддерево — это вершина вместе со *всеми* её потомками. Поддерево называется деревом поиска, если у каждой его вершины все значения в левой ветке строго меньше значения вершины, а все значения в правой ветке — строго больше.
Найдите поддерево поиска с наибольшей суммой значений и верните эту сумму. Пустое поддерево тоже считается деревом поиска, его сумма равна 0 — поэтому ответ никогда не бывает отрицательным.
Попробуйте обойти дерево за один проход.root=tree_node([6, 9, 12, 7, 11, 10, 15]) → 37
Корень 6 и его левая ветка нарушают порядок, а правая ветка 12 → (10, 15) — дерево поиска с суммой 12 + 10 + 15 = 37. Это больше, чем у ветки 9 → (7, 11): 27.
root=tree_node([2, 1, 3, None, None, -5, 4]) → 4
Всё дерево не подходит: -5 стоит справа от 2, хотя меньше его. Из подходящих поддеревьев лучшее — одиночная вершина 4 (поддерево 3 → (-5, 4) даёт только 2).
root=tree_node([-3, -8, -1]) → 0
Все значения отрицательные, поэтому выгоднее взять пустое поддерево с суммой 0.
Node.val ≤ 4·10⁴root=tree_node([6, 9, 12, 7, 11, 10, 15])
37
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 99 тестов на сервере, включая скрытые.