Почему это работает
- Вызов возвращает none ровно тогда, когда в его поддереве нет ни p, ни q, поэтому в каждом узле left и right говорят, с какой стороны они лежат.
- Если что-то нашлось с обеих сторон, p и q разошлись по разным поддеревьям, и ни один узел ниже не держит обоих: этот узел — самый низкий. Каждый вызов выше получает ответ только с одной стороны и просто передаёт его наверх.
- Если бы p лежал выше q, вызов на p сразу вернул бы p, не заглядывая ниже, и это верно: q где-то под p, значит, ответ — p.
Сложность
Время O(n): каждый узел посещаем не больше одного раза. Память O(h), где h — высота дерева: в стеке вызовов лежит один путь.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗