Faça um algoritmo que crie uma lista ligada com os nós de uma árvore binária em um percurso em-ordem.

Passo 1

O enunciado pede um algoritmo que, dado o ponteiro da raiz de uma árvore binária, construa uma lista simplesmente ligada contendo os nós da árvore obedecendo a ordem em-ordem (esquerda, raiz, direita). Vamos usar o conceito de percurso em-ordem e ir inserindo cada valor na cauda da lista.

Passo 2

Primeiro, precisamos definir a estrutura da lista ligada: cada nó da lista terá um campo para o valor e um ponteiro para o próximo nó. Também mantemos dois ponteiros auxiliares: head (cabeça) e tail (cauda) da lista.

Passo 3

O percurso em-ordem é uma técnica recursiva em que, para cada nó n, visitamos recursivamente sua subárvore esquerda, processamos n e depois visitamos recursivamente sua subárvore direita. Aqui, “processar” significa inserir o valor de n no final da lista.
Para inserir no final da lista, verificamos se head é nulo. Se for, o novo nó torna-se head e tail. Caso contrário, fazemos tail.next apontar para o novo nó e atualizamos tail para esse novo nó.

Passo 4

Unimos tudo em uma função principal createInOrderList que recebe root, inicializa head e tail, chama a função recursiva inOrder(root) e retorna head.
O algoritmo termina retornando o ponteiro head, que representa a lista ligada contendo todos os nós da árvore em ordem em-ordem.

Resposta

// Estruturas de dados
class TreeNode {
int val;
TreeNode left;
TreeNode right;
}
class ListNode {
int val;
ListNode next;
}
// Função principal
ListNode createInOrderList(TreeNode root) {
ListNode head = null;
ListNode tail = null;
// Função auxiliar para inserir no final da lista
void append(int x) {
    ListNode novo = new ListNode();
    novo.val = x;
    novo.next = null;
    if (head == null) {
        head = novo;
        tail = novo;
    } else {
        tail.next = novo;
        tail = novo;
    }
}

// Percurso em-ordem recursivo
void inOrder(TreeNode node) {
    if (node == null) return;
    inOrder(node.left);
    append(node.val);
    inOrder(node.right);
}

inOrder(root);
return head;
}

Exercícios relacionados