Зеркальное отражение бинарного дерева

Условие

Для переданного корня дерева root выполнить его зеркальное отражение (инвертировать) и вернуть полученный корень.

function TreeNode(val, left, right) {
    this.val = (val === undefined ? 0 : val)
    this.left = (left === undefined ? null : left)
    this.right = (right === undefined ? null : right)
}

Примеры:

      1           1
     / \         / \
    2   3  =>   3   2
        1           1
       / \         / \
      2   3  =>   3   2
     / \ / \     / \ / \
    4  5 6 ?    ? 6 5  4

Ответ

Поменяйте левую и правую ветви местами у каждого узла. Можно выполнить итеративный обход со стеком и вернуть тот же корень.

function invertTree(root) {
  if (!root) return root;
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    [node.left, node.right] = [node.right, node.left];
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }
  return root;
}

Время O(n), дополнительная память O(h) для глубины дерева в DFS. Реализация изменяет исходное дерево; если требуется неизменяемость, вместо перестановки создавайте новые узлы.