Это первая задача на деревья, поэтому сперва определимся, что это за структура данных. Кстати, рассказать об этом интервьюеру, уточнив, что вы с ним понимаете о чем идёт речь одинаково, может быть не лишним.
Узлом назовём объект следующего вида:
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
Каждый узел содержит две ссылки на другие узлы, которые условно называются дочерними. Т.к. их два — отсюда и «бинарное дерево» (по аналогии, существуют n-арные деревья, т.е. с n количеством дочерних узлов).
Итак, что же такое развернуть?
4 4
/ \\ / \\
2 7 --> 7 2
/ \\ / \\ / \\ / \\
1 3 6 9 9 6 3 1
Дерево будто отражается в зеркале: каждый левый узел становится правым.
Кстати, эта та самая задачка о которой писал Max Howell, автор Homebrew, которого не взяли в Google 😄
https://twitter.com/mxcl/status/608682016205344768
Решение становится понятным если попробовать развернуть дерево «руками», узел за узлом, и последить за тем, что мы делаем.
Представим сперва тривиальный случай:
4 4
/ \\ / \\
2 7 --> 7 2
Мы просто переставили левый и правый узел местами:
const tmp = root.left;
root.left = root.right;
root.right = tmp;
Исходное дерево после такой операции будет выглядеть так:
4 4
/ \\ / \\
2 7 --> 7 2
/ \\ / \\ / \\ / \\
**1 3 6 9 6 9 1 3**
Обратите внимание на последний ряд узлов — они не поменялись относительно своих родителей, потому что мы поменяли местами только непосредственных детей корня (4) и на этом остановились, а нужно сделать то же самое рекурсивно для их детей.
В любой рекурсии важно понимать о том, когда нужно остановиться, это называется базовый случай. В данном случае это когда узлы кончились, т.е. на вход получили null, ничего.