Encontrando o Valor na Posição Inferior Esquerda de uma Árvore Binária (Problema 513)
Determinar o valor do nó mais à esquerda na camada mais profunda de uma árvore binária é um problema que pode ser eficientemente resolvido utilizando uma abordagem de travessia em largura (BFS). Esta técnica permite processar a árvore nível por nível, garantindo que o primeiro nó encontrado em cada nível seja o mais à esquerda desse nível. Ao final da travessia, o último valor registrado para o nó mais à esquerda será, por definição, o do nó mais à esquerda da camada mais profunda.
from collections import deque
from typing import Optional, List
# Definição para um nó de árvore binária.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def encontrarValorEsquerdaInferior(self, raiz: Optional[TreeNode]) -> int:
if not raiz:
# Em um cenário real, a especificação do problema definiria o comportamento para uma árvore vazia.
# Aqui, para simplificar, pode-se retornar 0 ou levantar um erro.
# Assumimos que a raiz não será None para este problema.
return 0
fila_nodos = deque()
fila_nodos.append(raiz)
# O valor inicial é o da raiz. Ele será atualizado a cada nível.
valor_esq_profundo = raiz.val
while fila_nodos:
# Captura o tamanho atual da fila para saber quantos nós há neste nível.
tamanho_nivel = len(fila_nodos)
for i in range(tamanho_nivel):
nodo_atual = fila_nodos.popleft()
# Se este é o primeiro nó do nível atual, ele é o nó mais à esquerda deste nível.
# Atualizamos nosso resultado provisório.
if i == 0:
valor_esq_profundo = nodo_atual.val
# Adiciona os filhos à fila para o próximo nível.
if nodo_atual.left:
fila_nodos.append(nodo_atual.left)
if nodo_atual.right:
fila_nodos.append(nodo_atual.right)
return valor_esq_profundo
Caminhos com Soma Alvo em Árvores Binárias
Os problemas de soma de camnihos em árvores binárias são clássicos para demonstrar o poder da recursão e do backtracking. Geralmente envolvem percorrer a árvore em profundidade (DFS), ajustando a soma alvo conforme se avança e avaliando condições em nós folha.
Verificando a Existência de um Caminho com Soma Alvo (Problema 112)
Neste problema, o objetivo é simplesmente verificar se existe qualquer caminho da raiz a uma folha cuja soma dos valores dos nós seja igual a um valor alvo específico. Uma abordagem recursiva que subtrai o valor do nó atual da soma alvo é bastante eficaz.
from typing import Optional
# Definição para um nó de árvore binária.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def verificaSomaCaminho(self, nodo_atual: Optional[TreeNode], soma_alvo_restante: int) -> bool:
# Caso base 1: Se o nó atual é nulo, não há caminho por aqui.
if not nodo_atual:
return False
# Caso base 2: Se o nó atual é uma folha, verificamos se a soma restante
# corresponde ao valor deste nó.
if not nodo_atual.left and not nodo_atual.right:
return nodo_atual.val == soma_alvo_restante
# Caso recursivo: Continua a busca nos filhos, subtraindo o valor do nó atual
# da soma_alvo_restante. A função retorna True se um caminho válido for encontrado
# em qualquer um dos lados.
# Tenta o caminho pela subárvore esquerda
encontrado_na_esquerda = self.verificaSomaCaminho(nodo_atual.left, soma_alvo_restante - nodo_atual.val)
if encontrado_na_esquerda:
return True # Se encontrado, não precisamos verificar o lado direito
# Tenta o caminho pela subárvore direita
encontrado_na_direita = self.verificaSomaCaminho(nodo_atual.right, soma_alvo_restante - nodo_atual.val)
return encontrado_na_direita
Encontrando Todos os Caminhos com Soma Alvo (Problema 113)
Em contraste com o problema anterior, este exige que se encontrem e retornem todas as sequências de nós (caminhos) da raiz a uma folha que somam o valor alvo. Isso exige uma técnica de backtracking, onde o caminho atual é construído e desconstruído durante a travessia.
from typing import Optional, List
# Definição para um nó de árvore binária.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def encontrarTodosCaminhosComSoma(self, raiz: Optional[TreeNode], soma_desejada: int) -> List[List[int]]:
todos_caminhos_encontrados = [] # Lista para armazenar todos os caminhos válidos
caminho_atual = [] # Lista para manter o caminho sendo explorado no momento
def dfs_backtracking(nodo: Optional[TreeNode], soma_restante: int):
# Condição de parada: Se o nó atual é nulo, encerra este ramo de busca.
if not nodo:
return
caminho_atual.append(nodo.val) # Adiciona o valor do nó atual ao caminho
# Se chegamos a um nó folha:
if not nodo.left and not nodo.right:
# Verificamos se a soma restante é igual ao valor deste nó folha.
# Se for, encontramos um caminho válido.
if soma_restante == nodo.val:
todos_caminhos_encontrados.append(list(caminho_atual)) # Adiciona uma cópia do caminho
else:
# Se não é uma folha, continua a busca nos filhos,
# diminuindo a soma restante pelo valor do nó atual.
dfs_backtracking(nodo.left, soma_restante - nodo.val)
dfs_backtracking(nodo.right, soma_restante - nodo.val)
# Passo de backtracking: Remove o valor do nó atual do caminho
# para que outros ramos possam ser explorados.
caminho_atual.pop()
dfs_backtracking(raiz, soma_desejada)
return todos_caminhos_encontrados
Reconstrução de Árvores Binárias a Partir de Percursos
A reconstrução de uma árvore binária a partir de seus percursos (travessias) é um problema fundamentla que explora as propriedades únicas de cada tipo de percurso (pré-ordem, em-ordem, pós-ordem). A chave está em como cada percurso revela a posição da raiz e a estrutura das subárvores.
Construindo uma Árvore a Partir de Percursos Pré-Ordem e Em-Ordem (Problema 105)
O percurso pré-ordem (raiz, esquerda, direita) sempre revela a raiz da subárvore atual como seu primeiro elemento. O percurso em-ordem (esquerda, raiz, direita) é crucial para identificar quais elementos pertencem à subárvore esquerda e quais à subárvore direita, uma vez que a raiz é localizada.
from typing import Optional, List
# Definição para um nó de árvore binária.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def construirArvorePreInorder(self, pre_ordem: List[int], em_ordem: List[int]) -> Optional[TreeNode]:
# Caso base: Se o percurso pré-ordem estiver vazio, não há árvore a construir.
if not pre_ordem:
return None
# O primeiro elemento do percurso pré-ordem é sempre a raiz da árvore ou subárvore atual.
valor_raiz = pre_ordem[0]
nodo_raiz = TreeNode(valor_raiz)
# Encontra a posição do valor da raiz no percurso em-ordem.
# Isso divide o percurso em-ordem em elementos da subárvore esquerda e direita.
indice_raiz_em_ordem = em_ordem.index(valor_raiz)
# Divide o percurso em-ordem para as subárvores esquerda e direita.
em_ordem_esq = em_ordem[:indice_raiz_em_ordem]
em_ordem_dir = em_ordem[indice_raiz_em_ordem + 1:]
# O número de elementos na subárvore esquerda em-ordem determina o tamanho
# dos respectivos segmentos no percurso pré-ordem.
tamanho_subarvore_esq = len(em_ordem_esq)
# Divide o percurso pré-ordem para as subárvores esquerda e direita.
# O pré-ordem esquerdo começa após a raiz (pre_ordem[1]) e tem o tamanho da subárvore esquerda.
pre_ordem_esq = pre_ordem[1 : 1 + tamanho_subarvore_esq]
# O pré-ordem direito começa após o segmento esquerdo no pré-ordem.
pre_ordem_dir = pre_ordem[1 + tamanho_subarvore_esq :]
# Constrói recursivamente as subárvores.
nodo_raiz.left = self.construirArvorePreInorder(pre_ordem_esq, em_ordem_esq)
nodo_raiz.right = self.construirArvorePreInorder(pre_ordem_dir, em_ordem_dir)
return nodo_raiz
Construindo uma Árvore a Partir de Percursos Em-Ordem e Pós-Ordem (Problema 106)
Similarmente, para percursos em-ordem e pós-ordem, o último elemento do percurso pós-ordem (esquerda, direita, raiz) sempre indica a raiz. O percurso em-ordem novamente serve para particionar os elementos entre as subárvores esquerda e direita, permitindo a construção recursiva.
from typing import Optional, List
# Definição para um nó de árvore binária.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def construirArvoreInPostorder(self, em_ordem: List[int], pos_ordem: List[int]) -> Optional[TreeNode]:
# Caso base: Se o percurso pós-ordem (ou em-ordem) estiver vazio, não há árvore a construir.
if not pos_ordem:
return None
# O último elemento do percurso pós-ordem é sempre a raiz da árvore ou subárvore atual.
valor_raiz = pos_ordem[-1]
nodo_raiz = TreeNode(valor_raiz)
# Encontra a posição do valor da raiz no percurso em-ordem.
# Isso divide o percurso em-ordem em elementos da subárvore esquerda e direita.
indice_raiz_em_ordem = em_ordem.index(valor_raiz)
# Divide o percurso em-ordem para as subárvores esquerda e direita.
em_ordem_esq = em_ordem[:indice_raiz_em_ordem]
em_ordem_dir = em_ordem[indice_raiz_em_ordem + 1:]
# O número de elementos na subárvore esquerda em-ordem determina o tamanho
# dos respectivos segmentos no percurso pós-ordem.
tamanho_subarvore_esq = len(em_ordem_esq)
# Divide o percurso pós-ordem para as subárvores esquerda e direita.
# O pós-ordem esquerdo contém os elementos da subárvore esquerda.
pos_ordem_esq = pos_ordem[:tamanho_subarvore_esq]
# O pós-ordem direito contém os elementos da subárvore direita,
# excluindo o último elemento (que já foi usado como raiz global).
pos_ordem_dir = pos_ordem[tamanho_subarvore_esq : -1]
# Constrói recursivamente as subárvores.
nodo_raiz.left = self.construirArvoreInPostorder(em_ordem_esq, pos_ordem_esq)
nodo_raiz.right = self.construirArvoreInPostorder(em_ordem_dir, pos_ordem_dir)
return nodo_raiz