Inversão de árvore binária com TypeScript

// Definição da estrutura do nó da árvore binária
class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;

  constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// Função para inverter a árvore binária (recursiva)
function invertTree(root: TreeNode | null): TreeNode | null {
  // Caso base: se o nó é null, retorna null
  if (root === null) {
    return null;
  }

  // Salva temporariamente o filho esquerdo
  const temp = root.left;

  // Troca os filhos
  root.left = root.right;
  root.right = temp;

  // Recursivamente inverte as subárvores
  invertTree(root.left);
  invertTree(root.right);

  return root;
}

// Versão iterativa usando pilha
function invertTreeIterative(root: TreeNode | null): TreeNode | null {
  if (root === null) {
    return null;
  }

  const stack: TreeNode[] = [root];

  while (stack.length > 0) {
    const node = stack.pop()!;

    // Troca os filhos
    const temp = node.left;
    node.left = node.right;
    node.right = temp;

    // Adiciona os filhos não-nulos à pilha
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }

  return root;
}

// Função auxiliar para imprimir a árvore (in-order traversal)
function printInOrder(root: TreeNode | null): number[] {
  if (root === null) return [];

  const result: number[] = [];
  const stack: TreeNode[] = [];
  let current: TreeNode | null = root;

  while (current !== null || stack.length > 0) {
    while (current !== null) {
      stack.push(current);
      current = current.left;
    }

    current = stack.pop()!;
    result.push(current.val);
    current = current.right;
  }

  return result;
}

// Exemplo de uso
console.log("=== Exemplo de Inversão de Árvore Binária ===");

// Criando a árvore original:
//       4
//      / \
//     2   7
//    / \ / \
//   1  3 6  9
const root = new TreeNode(4);
root.left = new TreeNode(2);
root.right = new TreeNode(7);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(9);

console.log("Árvore original (in-order):", printInOrder(root));

// Invertendo a árvore
const invertedRoot = invertTree(root);

console.log("Árvore invertida (in-order):", printInOrder(invertedRoot));

// A árvore invertida ficará assim:
//       4
//      / \
//     7   2
//    / \ / \
//   9  6 3  1