Какие условия выхода нужны для рекурсивного метода зеркалирования дерева?

Что проверяют

Видите ли вы базовый случай рекурсии и понимаете ли, почему для зеркалирования достаточно одного. Следом обычно просят оценить сложность, сказать, что будет на вырожденном дереве, и переписать решение без рекурсии.

Как отвечать

Зеркалирование меняет местами левого и правого потомка у каждого узла. Обязательное условие выхода одно:

• node == null: пустое поддерево уже зеркально само себе, возвращаем null и дальше не идём. Эта проверка покрывает и пустое дерево на входе, и детей листьев;
• лист (left == null && right == null): можно вернуть узел сразу, но это экономия пары вызовов, а не отдельное условие. Без неё код остаётся корректным, потому что оба рекурсивных вызова упрутся в null.

Порядок действий внутри: сохранить node.left во временную переменную, рекурсивно отзеркалить оба поддерева и присвоить их крест-накрест. Если написать node.left = mirror(node.right), а следом node.right = mirror(node.left), второй вызов получит уже изменённую ссылку: исходное левое поддерево потеряется, а правое окажется отзеркаленным дважды.

Сложность: время O(n), каждый узел посещается один раз. Память O(h) на стек вызовов, где h это высота дерева: O(log n) для сбалансированного и O(n) для вырожденного в список. На вырожденном дереве из десятков тысяч узлов при размере стека по умолчанию (-Xss) легко получить StackOverflowError. Поэтому хорошо сразу предложить итеративный вариант: обход в ширину через ArrayDeque<TreeNode>, где у каждого извлечённого узла меняются местами дети, а ненулевые дети кладутся в очередь.

Где спотыкаются

Проверяют node.left == null вместо node == null и получают NullPointerException, когда на вход приходит пустое дерево.

Присваивают поддеревья без временной переменной, как описано выше, и одна ветка затирается. Такой код часто проходит тест на дереве из трёх узлов и ломается на большем.

Не могут объяснить, чем рискует рекурсия на глубоком дереве, и не знают, что JVM не устраняет хвостовые вызовы. Переписать решение «в хвостовую рекурсию» в Java ничего не даст, спасает только явный стек или очередь.