0633-arvore-basica

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: '1.0' id: 633 name: Arvore Basica origin: wok slug: arvore-basica authorSlugEditorial: alessio authorSlugProblem: alessio description: Construa uma árvore binária a partir de relações pai-filho fornecidas e extraia suas propriedades fundamentais. O desafio consiste em processar as conexões dinamicamente e realizar uma travessia em ordem (ERD) seguida pelo cálculo da altura da árvore. editorial: 'Para resolver este problema, utilize uma estrutura de nós (struct ou classe) contendo o ID e referências para os filhos esquerdo e direito. Como os IDs dos nós são únicos, use um mapa (hash map ou array de pointers) para armazenar e recuperar nós existentes rapidamente. Para cada linha de entrada, vincule o nó pai aos seus filhos conforme especificado. Após montar a árvore completa (indicada pelo EOF), realize uma travessia recursiva In-Order (Esquerda-Raiz-Direita) para a impressão e utilize uma função recursiva de altura: 1 + max(altura_esquerda, altura_direita). A complexidade final de tempo e espaço é linear em relação ao número de nós.' successmsg: Parabéns! Você demonstrou domínio sobre a construção manual de árvores e algoritmos recursivos de travessia. difficultyLevelId: C timeComplexity: O(N) timeLimitSegs: 1 memoryLimitMb: 128 defaultStatement: a_pt_arvore-basica skills: - logica - arvores - hashing - io - recursividade statements: - id: a-arvore-basica testScenarioLevel: A thematicSkills: - skill: fantasy-fiction points: 1 testScenarios: - id: d-sample name: Exemplos do Enunciado (Sample) description: Casos de teste idênticos aos apresentados na especificação do problema para garantir conformidade básica com os exemplos fornecidos. helpTip: Verifique se sua saída segue exatamente o formato dos exemplos (espaços e quebras de linha). level: D testType: TDD skills: - skill: trees points: 1 - skill: binary-tree-traversals points: 1 - id: c-logic-single-children name: Lógica de Filhos Únicos description: Valida a regra "2 números = filho esquerdo" e testa nós que possuem apenas o filho da direita ou esquerda de forma mista. helpTip: Lembre-se que se uma linha tiver apenas 2 números, o segundo é obrigatoriamente o filho da ESQUERDA. level: C testType: TDD skills: - skill: trees points: 1 - skill: selection points: 1 - id: b-edge-minimal-root name: Caso Base (Raiz Única) description: Árvore contendo apenas o nó raiz. Testa se a altura é reportada como 1 e se a travessia funciona para um único elemento. helpTip: 'Verifique como sua lógica se comporta no menor cenário possível: uma árvore com apenas um elemento.' level: B testType: TDD skills: - skill: basic-logic points: 1 - id: b-edge-zigzag-unbalanced name: Árvore em Zig-Zag description: Árvore que alterna filhos à esquerda e direita em cada nível. Testa neutralidade de lado na construção e cálculo de altura. helpTip: Verifique se sua lógica de altura e travessia funciona corretamente quando os filhos alternam entre os lados a cada nível. level: B testType: TDD skills: - skill: recursion points: 1 - skill: binary-tree-traversals points: 1 - id: c-logic-fragmented-input name: Entrada Fragmentada (Pai Repetido) description: Define filhos de um mesmo pai em linhas de entrada separadas para validar a atualização dinâmica de nós existentes. helpTip: Os filhos de um nó nem sempre vêm na mesma linha da entrada. Sua solução consegue atualizar um nó já criado? level: C testType: TDD skills: - skill: hashing points: 1 - skill: trees points: 1 - id: b-edge-deep-skewed name: Árvore Degenerada (Pilha de Recursão) description: Uma árvore linear e muito profunda (10.000 nós em linha). Testa se a implementação recursiva estoura a pilha ou se o cálculo de altura é eficiente. helpTip: Árvores muito profundas podem causar erro de 'Stack Overflow'. Você está usando recursão de forma segura ou um método iterativo? level: B testType: TDD skills: - skill: recursion points: 1 - skill: complexity-analysis points: 1 - id: a-performance-load name: Teste de Carga e IDs Grandes (O(N)) description: Cenário com 10.000 nós e identificadores não sequenciais de até 1.000.000. Força o uso eficiente de tempo e memória. helpTip: Com IDs chegando a 1.000.000, um array simples pode desperdiçar memória. Use um Map ou Dicionário para gerenciar os nós de forma O(1). level: A testType: TDD skills: - skill: hashing points: 1 - skill: trees points: 1 - skill: complexity-analysis points: 1 solutions: - id: a-optimal name: Solução Ótima (O(N)) description: Constrói a árvore utilizando um dicionário/mapa para acesso instantâneo aos nós, garantindo complexidade linear de tempo e espaço. level: A implementations: - filenames: - arvore.cpp language: cpp paradigm: Imperative - filenames: - Arvore.java language: java paradigm: Imperative main: Arvore - filenames: - arvore.py language: py paradigm: Imperative - id: b-brute-force name: Brute Force (O(N^2)) description: Realiza busca linear em uma lista para encontrar o pai de cada nó durante a construção, resultando em desempenho quadrático. level: B implementations: - filenames: - brute.py language: py paradigm: Imperative - id: c-wrong-order name: Wrong Order (WA) description: Realiza a travessia em Pré-ordem (RED) em vez de Em-ordem (ERD), servindo para validar a detecção de Wrong Answer pelo corretor. level: C implementations: - filenames: - wa.py language: py paradigm: Imperative author: Unknown topics: - arvores-binarias