Diâmetro, Altura e Árvores Balanceadas
Calcule o diâmetro e a altura de uma árvore em uma única passagem DFS usando uma função auxiliar que retorna ambos os valores e verifique se a árvore é balanceada por altura.
Diâmetro, Altura e Árvores Balanceadas é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
Altura de uma árvore binária
A altura (ou profundidade máxima) de uma árvore binária é o comprimento do caminho mais longo da raiz até qualquer folha. Ela é calculada recursivamente: a altura de qualquer nó é 1 + max(height(left), height(right)), com um caso-base de 0 para nós nulos. Esse cálculo em pós-ordem é fundamental — a altura é o componente básico do diâmetro, da verificação de balanceamento e das rotações de árvores AVL.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def height(root):
if not root:
return 0
return 1 + max(height(root.left), height(root.right))
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.left.left.left = TreeNode(6)
print(height(root)) # 4Diâmetro: o caminho mais longo
O diâmetro de uma árvore binária é o comprimento do caminho mais longo entre dois nós quaisquer (o caminho pode passar ou não pela raiz). O comprimento do caminho é medido em arestas. Para qualquer nó, o diâmetro que passa por ele é igual a height(left) + height(right). O diâmetro geral é o maior valor desse tipo entre todos os nós da árvore.
def diameter_of_binary_tree(root):
max_diameter = [0] # use list to allow closure mutation
def dfs(node):
if not node:
return 0
left_h = dfs(node.left)
right_h = dfs(node.right)
# Diameter through this node
max_diameter[0] = max(max_diameter[0], left_h + right_h)
return 1 + max(left_h, right_h) # height for parent
dfs(root)
return max_diameter[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_of_binary_tree(root)) # 3Uma única passagem de DFS para o diâmetro
A abordagem ingênua chama height() em todos os nós — O(n²) para uma árvore balanceada. A solução ideal calcula a altura e atualiza o diâmetro em uma única passagem de DFS. A ideia principal é que a função recursiva dfs() cumpre duas finalidades simultaneamente: retorna a altura para o pai e atualiza um diâmetro máximo global como efeito colateral. Esse padrão de pós-ordem com dupla finalidade aparece em muitos problemas de árvores.
# O(n^2) NAIVE: recomputes height for every node
def diameter_naive(root):
if not root:
return 0
through_root = height(root.left) + height(root.right)
in_left = diameter_naive(root.left)
in_right = diameter_naive(root.right)
return max(through_root, in_left, in_right)
# O(n) OPTIMAL: single DFS pass (shown in previous scene)
# The naive version is O(n^2) because height() is O(n)
# and it is called for every node.
print('Naive: O(n^2) | Optimal single-pass: O(n)')Verificação de árvore binária balanceada
Uma árvore binária é balanceada por altura se as alturas das subárvores esquerda e direita de cada nó diferem no máximo em um. A abordagem de força bruta chama height() em todos os nós — O(n²). A abordagem ideal usa o mesmo truque de uma única passagem: retorne -1 como sentinela para indicar 'não balanceada' e propague esse valor para cima, interrompendo o processamento assim que qualquer nó for considerado desbalanceado.
def is_balanced(root):
def check(node):
if not node:
return 0
left = check(node.left)
if left == -1:
return -1 # propagate early exit
right = check(node.right)
if right == -1:
return -1
if abs(left - right) > 1:
return -1 # unbalanced here
return 1 + max(left, right) # height if balanced
return check(root) != -1
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.left.left = TreeNode(5) # too deep on left
print(is_balanced(root)) # FalseO padrão do valor de retorno sentinela
Retornar um valor sentinela (-1 para indicar desbalanceamento ou uma tupla especial) é um padrão comum quando um auxiliar de DFS precisa sinalizar dois tipos de informação: o resultado calculado e se uma restrição foi violada. Em vez de lançar exceções ou usar indicadores globais, codifique o erro no tipo de retorno. Essa abordagem é simples, evita o estado global e integra-se naturalmente a outros auxiliares recursivos.
# General pattern: return (is_valid, computed_value)
def balanced_height(node):
if not node:
return True, 0
left_ok, left_h = balanced_height(node.left)
if not left_ok:
return False, 0 # short-circuit
right_ok, right_h = balanced_height(node.right)
if not right_ok:
return False, 0
balanced = abs(left_h - right_h) <= 1
return balanced, 1 + max(left_h, right_h)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
ok, h = balanced_height(root)
print(ok, h) # True 2Diâmetro em termos de nós e arestas
Tenha cuidado com o enunciado do problema: o LeetCode #543 mede o diâmetro em arestas, enquanto alguns problemas o medem em nós. Se precisar da contagem de nós, o diâmetro que passa por um nó é height(left) + height(right) + 1 (adicione 1 para o próprio nó). Se precisar da contagem de arestas, omita o +1. Sempre esclareça isso com o entrevistador antes de programar.
def diameter_in_nodes(root):
max_path = [0]
def dfs(node):
if not node:
return 0
left_h = dfs(node.left)
right_h = dfs(node.right)
# Path through this node in NODE count
nodes_through = left_h + right_h + 1
max_path[0] = max(max_path[0], nodes_through)
return 1 + max(left_h, right_h)
dfs(root)
return max_path[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_in_nodes(root)) # 4 nodes: 4-2-1-3 or 5-2-1-3Soma do caminho: qualquer caminho da raiz até uma folha
O problema da soma do caminho pergunta: a soma dos valores de algum caminho da raiz até uma folha é igual a um valor-alvo? Use DFS e subtraia o valor do nó atual do valor-alvo à medida que desce. Em uma folha, verifique se o valor-alvo restante é igual ao valor da folha. Este é um DFS em pré-ordem no qual você passa a soma restante como parâmetro — um exemplo clássico de recursão de cima para baixo.
def has_path_sum(root, target):
if not root:
return False
# Leaf node: check if we've exactly hit the target
if not root.left and not root.right:
return root.val == target
remaining = target - root.val
return (has_path_sum(root.left, remaining) or
has_path_sum(root.right, remaining))
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
print(has_path_sum(root, 22)) # True: 5+4+11+2=22Soma máxima de um caminho (variante difícil)
A soma máxima de um caminho (LeetCode #124) é significativamente mais difícil: o caminho pode começar e terminar em qualquer nó, não apenas da raiz até uma folha, e os valores podem ser negativos. Em cada nó, considere quatro opções: apenas o nó, nó + ramo esquerdo, nó + ramo direito ou nó + ambos os ramos. Apenas as três primeiras podem se estender até o pai; a quarta é uma candidata terminal para o máximo global.
def max_path_sum(root):
max_sum = [float('-inf')]
def gain(node):
if not node:
return 0
# Only take positive contributions
left = max(gain(node.left), 0)
right = max(gain(node.right), 0)
# Best path through this node (can't go both ways upward)
max_sum[0] = max(max_sum[0], node.val + left + right)
# Return the best single-branch gain for parent
return node.val + max(left, right)
gain(root)
return max_sum[0]
root = TreeNode(-10)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(max_path_sum(root)) # 42: 15+20+7Árvores AVL e autobalanceamento
Uma árvore AVL é uma BST que mantém a propriedade de balanceamento por altura ao realizar rotações após operações de inserção e exclusão. Cada nó armazena um fator de balanceamento (altura(direita) - altura(esquerda)), que deve permanecer em {-1, 0, 1}. Quando ocorre uma violação, uma rotação simples ou dupla restaura o balanceamento em O(1), mantendo a altura geral em O(log n) e garantindo que todas as operações tenham complexidade O(log n).
# Balance factor = height(right) - height(left)
# AVL invariant: balance factor in {-1, 0, 1} for every node
# Four violation types and their fixes:
# LL (left-heavy left child): single right rotation
# RR (right-heavy right child): single left rotation
# LR (right-heavy left child): left rotate child, then right rotate root
# RL (left-heavy right child): right rotate child, then left rotate root
# Knowing this is enough for interviews; you rarely implement
# full AVL in an interview but must discuss the concept.
print('AVL maintains O(log n) height via rotations')Verificação de árvore simétrica
Uma árvore binária é simétrica se for uma imagem espelhada de si mesma. Verifique recursivamente: a árvore é simétrica se, para cada par de nós correspondentes em lados opostos do eixo, eles tiverem valores iguais e suas subárvores forem imagens espelhadas umas das outras. Defina um auxiliar is_mirror(left, right) que verifique: ambos nulos (tudo certo), um nulo (não), valores iguais e subárvores internas e externas espelhadas.
def is_symmetric(root):
def is_mirror(left, right):
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val and
is_mirror(left.left, right.right) and
is_mirror(left.right, right.left))
return is_mirror(root.left, root.right)
sym = TreeNode(1)
sym.left = TreeNode(2)
sym.right = TreeNode(2)
sym.left.left = TreeNode(3)
sym.right.right = TreeNode(3)
print(is_symmetric(sym)) # True
nosym = TreeNode(1)
nosym.left = TreeNode(2)
nosym.right = TreeNode(2)
nosym.left.right = TreeNode(3)
print(is_symmetric(nosym)) # FalseCombinando informações de altura e diâmetro
O padrão de pós-ordem em uma única passagem, no qual uma função auxiliar retorna simultaneamente a altura e atualiza um resultado global, pode ser reutilizado em muitos problemas: diâmetro, soma máxima de caminhos, verificação do balanceamento, contagem de nós bons e muito mais. Pergunte sempre: “de quais informações o pai precisa de cada filho?”. Essa é a informação retornada. “Qual cálculo é local a este nó?”. Esse cálculo atualiza a resposta global. Essa decomposição é a habilidade fundamental para resolver problemas difíceis de árvores.
# Reusable template for post-order dual-purpose DFS:
def tree_problem(root):
result = [float('-inf')] # or 0 depending on problem
def dfs(node):
if not node:
return 0 # base return (height, count, etc.)
left_val = dfs(node.left)
right_val = dfs(node.right)
# --- Update global result using both children ---
candidate = left_val + right_val # example: diameter
result[0] = max(result[0], candidate)
# --- Return info needed by PARENT ---
return 1 + max(left_val, right_val) # example: height
dfs(root)
return result[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(tree_problem(root)) # diameter = 2Verificação rápida
Verifique sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu: cálculo da altura usando DFS recursivo em pós-ordem, cálculo do diâmetro em uma única passagem O(n) usando uma função auxiliar de DFS com duas finalidades e verificação do balanceamento com uma sentinela de saída antecipada. A seguir, abordaremos problemas de soma de caminhos e o menor ancestral comum.
Perguntas Frequentes
A aula “Diâmetro, Altura e Árvores Balanceadas” é grátis?
Sim — o texto completo de “Diâmetro, Altura e Árvores Balanceadas” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “Diâmetro, Altura e Árvores Balanceadas”?
Calcule o diâmetro e a altura de uma árvore em uma única passagem DFS usando uma função auxiliar que retorna ambos os valores e verifique se a árvore é balanceada por altura. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Diâmetro, Altura e Árvores Balanceadas”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de DSA Interview Prep?
Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Classe TreeNode e BFS por Níveis
- DFS em Ordem, Pré-Ordem e Pós-Ordem
- Diâmetro, Altura e Árvores Balanceadas
- Soma de Caminhos e Ancestral Comum Mais Baixo