Почему это работает
- Глубина дерева — это корень плюс глубина его более глубокого поддерева, а каждое поддерево — такое же дерево поменьше, поэтому хватает одного вызова на узел.
- Узел отвечает только после того, как ответили обе его стороны, поэтому первый найденный лист, 4, ничего не решает в одиночку: корень сравнивает 1 и 3.
- Пустой потомок возвращает 0, и лист получает 1 + max(0, 0) = 1 без отдельной проверки.
Сложность
Время O(n): по одному вызову на узел и на каждого пустого потомка. Память O(h), где h — высота дерева: в стеке вызовов лежит один путь от корня.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗