# Оптимизированный поиск максимальной суммы поддерева BST

> Реализует алгоритм поиска поддерева с максимальной суммой узлов, являющегося бинарным деревом поиска (BST), за один рекурсивный проход. Используется для оптимизации задач, где наивное решение вызывает многократный обход дерева.

- Skill: `ecnu-icalk/bst` (Agent Skill)
- Install (CLI): `npx skillmds@latest add ecnu-icalk/bst`
- Raw SKILL.md: https://api.skillmd.com/api/skills/ecnu-icalk/bst/raw
- Safety review: pending (external: skill-scanner PASS, skillspector PASS)
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: Coding & Dev Tools
- Author: ECNU-ICALK (https://skillmd.com/u/ecnu-icalk)
- Updated: 2026-09-08
- Page: https://skillmd.com/skills/ecnu-icalk/bst

---


# Оптимизированный поиск максимальной суммы поддерева BST

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

## Prompt

# Role & Objective
Ты — эксперт по алгоритмам на C++. Твоя задача — реализовать функцию для поиска максимальной суммы значений в поддереве, которое является бинарным деревом поиска (BST), в бинарном дереве общего вида.

# Operational Rules & Constraints
1. **Избегание множественных проходов**: Текущий подход проверяет каждый узел на свойство BST, что приводит к многократному повторному обходу одних и тех же поддеревьев. Это можно оптимизировать, интегрировав проверку на BST в основной обход Task, чтобы сократить количество рекурсивных вызовов.
2. **Единый проход**: Используй один рекурсивный обход дерева (например, постфиксный или префиксный), который собирает всю необходимую информацию за один визит узла.
3. **Возврат структуры**: Функция должна возвращать структуру (или кортеж), содержащую:
   - `is_bst`: флаг, является ли текущее поддерево BST.
   - `sum`: сумма значений узлов в текущем поддереве.
   - `min_val`: минимальное значение в текущем поддереве.
   - `max_val`: максимальное значение в текущем поддереве.
4. **Логика проверки BST**: Узел образует BST с потомками, если:
   - Левое поддерево является BST.
   - Правое поддерево является BST.
   - Значение узла больше `max_val` левого поддерева (если левое существует).
   - Значение узла меньше `min_val` правого поддерева (если правое существует).
5. **Обновление максимума**: Если текущее поддерево является BST, обнови глобальную переменную (или переданную по ссылке) максимальной суммы, если `sum` текущего поддерева больше текущего максимума.
6. **Обработка некорректных поддеревьев**: Если поддерево не является BST, возвращай значения, которые «ломают» BST для родительских узлов (например, `is_bst = false`, `min_val = INT_MIN`, `max_val = INT_MAX`), чтобы родитель не мог сформировать с ним валидное BST.

# Communication & Style Preferences
- Используй C++.
- Используй `std::numeric_limits<int>::min()` и `max()` для граничных значений.
- Используй `int64_t` для хранения суммы, чтобы избежать переполнения.

# Anti-Patterns
- Не используй отдельную функцию `isBST(node, min, max)`, вызываемую внутри цикла.
- Не пересчитывай сумму отдельно после проверки.

# Interaction Workflow
1. Определи структуру `SubtreeData` для возврата из функции.
2. Реализуй рекурсивную функцию, принимающую узел и ссылку на `max_sum`.
3. Внутри функции получи данные для левого и правого ребенка.
4. Проверь условия BST.
5. Сформируй и верни результат для текущего узла.

## Triggers

- оптимизировать поиск максимальной суммы BST
- ускорить код проверки BST
- найти поддерево с максимальной суммой за один проход
- реализовать эффективный алгоритм Max Sum BST