BastterCode semana 10 - Antes late do que never - 94. Binary Tree Inorder Traversal

Tecnologia
Giovanni  
em 18/03/23 8:46

Comentários

Último comentário 1º comentário do autor Só moderadores Só quem eu sigo Ordenar por gostei
FlyCavok  
em 18/03/2023 11:36
Segue o código em Dart

Dart não tem stack, mas a Queue também faz o papel de stack na implementação deles.

Obs: solução não recursiva

import "dart:collection";

class StackVal {
    final TreeNode node;
    final bool readValueOnly;
    
    StackVal(this.node, this.readValueOnly);
}

class Solution {
    
  final queue = Queue<StackVal>();
    
  List<int> inorderTraversal(TreeNode? root) {
      List<int> resp = [];
      if (root == null) return resp;
      
      queue.addLast(StackVal(root, false));
      
      while(!queue.isEmpty) {
          StackVal n = queue.removeLast();
          
          if (n.readValueOnly) {
              resp.add(n.node.val);
              continue;
          }

          if (n.node.right != null)
              queue.addLast(StackVal(n.node.right!, false));

          queue.addLast(StackVal(n.node, true));

          if (n.node.left != null)
              queue.addLast(StackVal(n.node.left!, false));
      }
      
      return resp;
      
  }
}
; 2; ; 0;
0 '; 0';
BastterCode semana 10 - Antes late do que never - 94. Binary Tree Inorder Traversal - #1 de 17
PMHM  
em 18/03/2023 16:59 
class Solution:
    def __init__(self):
        self.result = []

    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return

        self.inorderTraversal(root.left)
        self.result.append(root.val)
        self.inorderTraversal(root.right)

        return self.result


Ver mais

Solução recursiva...
; 0; ; 0;
0 '; 0';
BastterCode semana 10 - Antes late do que never - 94. Binary Tree Inorder Traversal - #2 de 17
PMHM  
em 18/03/2023 17:47
Refatorando, para simplificar o return

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        def transverse(root):
            if root:
                transverse(root.left)
                result.append(root.val)
                transverse(root.right)
        result = []
        transverse(root)
        return result
; 0; ; 0;
0 '; 0';
BastterCode semana 10 - Antes late do que never - 94. Binary Tree Inorder Traversal - #3 de 17
oxe  
em 18/03/2023 18:18
Ainda não consegui fazer sem recursão. Vou chegar lá...
class Solution {
public:
    vector<int> ans{};
    vector<int> inorderTraversal(TreeNode* root) {return inOrder(root);}
    
    vector<int> inOrder(TreeNode* r)  {
        if (r) {
            inOrder(r->left);
            ans.push_back(r->val);
            inOrder(r->right);
        }
        return ans;
    }
};?

; 1; ; 0;
0 '; 0';
BastterCode semana 10 - Antes late do que never - 94. Binary Tree Inorder Traversal - #4 de 17
oxe  
em 21/03/2023 18:12
Hoje tive mais tempo para pensar no problema com cuidado e entender melhor como funciona essa travessia inOrder. Consegui finalmente fazer um código sem recursão.

Inicialmente tinha pensado em apenas emular o código recursivo numa versão iterativa. Mas haveria um bocado de ineficiência nessa abordagem, pois eu teria que descer desde a raiz de novo toda vez que precisasse pegar um novo valor.

Então achei que seria mais inteligente armazenar os endereços dos nós da árvore em um vetor, o que me permitiria percorrer apenas uma vez cada nó para escrever no vetor e depois iterar o vetor e ir excluindo os nós já utilizados.

Assim. independente de quantos ramos a árvore tenha, eu poderia analisar apenas os nós relevantes e evitar ter que atravessar toda a árvore novamente para achar os nós das pontas.

Segue o código com comentários.
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        /* inOrder significa que vai percorrer todo o lado esquerdo
        da árvore, até chegar ao último nó da esquerda. 
        
        Depois, se tiver ramo à direita desse último nó da esquerda,
        percorre todo o lado esquerdo desse ramo à direita. 
        
        Se não tiver ramo à direita, sobe um nível e verifica 
        se tem ramo à direita do nó de cima.
        
        Assim sucessivamente, até chegar à raiz e descer pelo lado 
        direito da árvore, sempre pegando o nó mais à esquerda 
        antes de subir ou de descer à direita. */
        
        vector<int> values{}; //vetor que armazena os valores
        vector<TreeNode*> nodes{root}; //vetor que armazena os endereços dos nós
        TreeNode* crt; //armazena o endereço do nó atual que está sendo analisado
        
        if (root) //verifica se tem raiz, ou seja, se a lista não é nula
        {
            if (root->left) {crt = root->left;} //percorre 1º o lado esquerdo
            else { //se n tiver lado esquerdo, pega valor da raiz e desce o direito
                values.push_back(root->val);
                nodes.pop_back(); 
                if (root->right) 
                {
                    crt = root->right;
                }
            }
            
            while (crt) {//enquanto tiver nó para analisar
                while (crt->left) //desce até o último nó da esquerda
                {
                    nodes.push_back(crt); //armazena todos os nós
                    crt = crt->left;
                }
                
                nodes.push_back(crt); //faltou o último, armazena tb
                values.push_back(crt->val); //chegou ao último nó da esquerda, pega valor
                   
                if (crt->right) //se tiver nó à direita, desce à direita
                {
                    nodes.pop_back(); //já pegou o valor do nó, pode tirar do vetor
                    crt = crt->right;
                } 
                else {
                    ::vector<TreeNode*>::reverse_iterator rit = nodes.rbegin();
                    for (rit; rit != nodes.rend(); rit++) 
                    { //percorre o vetor de nós pelo fim, indo até a raiz da árvore
                        TreeNode* temp = *rit; //pega o endereço do nó
                        nodes.pop_back(); //exclui nó do vetor, n será mais preciso
                        if (temp->left) 
                        { //se o nó tiver caminho pela esquerda, ainda não pegou valor dele
                            values.push_back(temp->val); //pega o valor
                            temp->left = nullptr; //anula o caminho da esquerda, evita duplicidade
                        }
                        if (temp->right) 
                        { //se tiver caminho pela direita, desce por lá e quebra o for
                            crt = temp->right;
                            break;
                        } else 
                        { //se n tiver caminho à direita, vai iterar até n ter mais nó pra olhar
                            if (nodes.size() == 0) {crt = nullptr;}
                        }
                    }
                }
            }
        }
       return values;
    }
};?



; 0; ; 0;
0 '; 0';
BastterCode semana 10 - Antes late do que never - 94. Binary Tree Inorder Traversal - #5 de 17
oxe  
em 21/03/2023 18:20
Eu tento fazer os comentários bem bonitinhos, formatados e tal, aí toda vez fica desconfigurado quando eu posto kkkkk

Aqui, sem os comentários, que é mais fácil de ler.
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        
        vector<int> values{};
        vector<TreeNode*> nodes{root};
        TreeNode* crt;
        
        if (root) {
            if (root->left) {crt = root->left;}
            else {
                values.push_back(root->val);
                nodes.pop_back();
                if (root->right) {
                    crt = root->right;
                }
            }
            
            while (crt) {
                while (crt->left) {
                    nodes.push_back(crt);
                    crt = crt->left;
                }
                
                nodes.push_back(crt);
                values.push_back(crt->val);
                   
                if (crt->right)
                {
                    nodes.pop_back();
                    crt = crt->right;
                } 
                else {
                    ::vector<TreeNode*>::reverse_iterator rit;
                    rit = nodes.rbegin();
                    for (rit; rit != nodes.rend(); rit++) {
                        TreeNode* temp = *rit;
                        nodes.pop_back();
                        if (temp->left) {
                            values.push_back(temp->val);
                            temp->left = nullptr;
                        }
                        if (temp->right) {
                            crt = temp->right;
                            break;
                        } else {
                            if (nodes.size() == 0) crt = nullptr;
                        }
                    }
                }
            }
        }
       return values;
    }
};?
; 2; ; 0;
0 '; 0';
BastterCode semana 10 - Antes late do que never - 94. Binary Tree Inorder Traversal - #6 de 17
oxe  
em 21/03/2023 18:47
@Giovanni   a propósito, não sei se esse desafio ficou sendo o da semana atual ou se vai ter outro, mas faltou atualizar o link no banner do site.
; 0; ; 0;
0 '; 0';
BastterCode semana 10 - Antes late do que never - 94. Binary Tree Inorder Traversal - #7 de 17
Giovanni  
em 22/03/2023 08:55
@gustavo por favor atualizar o tópico da semana para esse
obrigado
; 1; ; 0;
0 '; 0';
BastterCode semana 10 - Antes late do que never - 94. Binary Tree Inorder Traversal - #8 de 17
Giovanni  
em 22/03/2023 08:57
 @oxe @PMHM @FlyCavok aproveitando, vocês que estão fazendo sempre, se quiserem sugerir questões para os próximos desafios (inclusive uma difícil para abril hehehe)

eu acabei ficando para trás nos meus estudos pessoais pq tive que mudar para outra linguagem, aí não sei qual nível de pergunta fica legal para colocar aqui

obrigado

; 1; ; 0;
0 '; 0';
BastterCode semana 10 - Antes late do que never - 94. Binary Tree Inorder Traversal - #9 de 17
gustavo  
em 22/03/2023 09:32
@Giovanni atualizado
a partir desse tá automático
; 1; ; 0;
0 '; 0';
BastterCode semana 10 - Antes late do que never - 94. Binary Tree Inorder Traversal - #10 de 17
PMHM  
em 23/03/2023 21:19

postado por @Giovanni em 22/03/2023 08:57:02

 oxe PMHM FlyCavok aproveitando, vocês que estão fazendo sempre, se quiserem sugerir questões para os próximos desafios (inclusive uma difícil para abril hehehe)

eu acabei ficando para trás nos meus estudos pessoais pq tive que mudar para outra linguagem, aí não sei qual nível de pergunta fica legal para colocar aqui

obrigado


Eu tô agarrado aqui também, Giovanni, hehehe... Então tô sem ideias para sugerir! Só posso dizer que eu já tô sambando nas fáceis/médias, imagina nas difíceis, hehehe Mas vamos até onde der
; 0; ; 0;
0 '; 0';
BastterCode semana 10 - Antes late do que never - 94. Binary Tree Inorder Traversal - #11 de 17
oxe  
em 23/03/2023 21:26
@Giovanni

Eu acho que esses desafios são mais uma porta de entrada pro pessoal. Considerando o alcance do site, toda hora vai ter gente nova entrando. Então acho que não é bom andar rápido demais.

Até porque mesmo o pessoal experiente pode se sentir desmotivado com questões muito difíceis. Afinal, é uma atividade extra, né? 

Então assim, por mim a gente continuaria com questões fáceis semanalmente e questões médias mensalmente. Pelo menos por enquanto. Mesmo no futuro, quando a gente tiver questões difíceis, acho que o ideal seria revezar.

Aí quem quiser e puder ir além disso, vai por fora, independente do site.

Acho que as melhores questões são aquelas que qualquer um consegue fazer, mesmo os mais iniciantes (embora talvez com alguma dificuldade), mas os mais experientes podem fazer melhor, com mais eficiência, usando alguma propriedade ou conceito mais avançado.
; 1; ; 0;
0 '; 0';
BastterCode semana 10 - Antes late do que never - 94. Binary Tree Inorder Traversal - #12 de 17
oxe  
em 24/03/2023 10:07
@Giovanni

Pro próximo desafio mensal, sugiro essa questão aqui, olha:

Design Circular Queue - LeetCode

O desafio é para construir um circular buffer com várias funções que ele descreve. É ótimo para entender melhor de data structures e de funções também.

Pro próximo desafio semanal, sugiro uma questão de matemática. Essa aqui parece bem legal:

Valid Perfect Square - LeetCode
; 0; ; 0;
0 '; 0';
BastterCode semana 10 - Antes late do que never - 94. Binary Tree Inorder Traversal - #13 de 17
FlyCavok  
em 30/03/2023 22:17
Legal Oxe, boa. 

@Giovanni

Eu tenho conta premium. Posso pegar uns exercícios. Vocês querem diversificação ou focar em um assunto?

Desculpem aí a ausência. To com bebê em casa, então minha agenda não é mais minha hahaha

Questão difícil em geral é bem complicada. Eu já fiquei uns 4 dias pra resolver uma. E olha que eu fiquei tão puto que não parei de pensar na questão... acho que o nível médio já tá bom

Aliás, a maioria das empresas americanas vão até as medium nas entrevistas.

Eu passei em uma entrevista esses dias com uma easy. Acreditem se quiser rsrsrs 

Não precisa de tanto assim, a menos que queiram ir para o Google.
; 2; ; 0;
0 '; 0';
BastterCode semana 10 - Antes late do que never - 94. Binary Tree Inorder Traversal - #14 de 17
Giovanni  
em 31/03/2023 08:23


postado por @FlyCavok em 30/03/2023 22:17

Legal Oxe, boa. 

Giovanni

Eu tenho conta premium. Posso pegar uns exercícios. Vocês querem diversificação ou focar em um assunto?

Desculpem aí a ausência. To com bebê em casa, então minha agenda não é mais minha hahaha

Questão difícil em geral é bem complicada. Eu já fiquei uns 4 dias pra resolver uma. E olha que eu fiquei tão puto que não parei de pensar na questão... acho que o nível médio já tá bom

Aliás, a maioria das empresas americanas vão até as medium nas entrevistas.

Eu passei em uma entrevista esses dias com uma easy. Acreditem se quiser rsrsrs 

Não precisa de tanto assim, a menos que queiram ir para o Google.


opa, o problema de pegar as premium é que o pessoal não vai conseguir rodar e testar
acho que por enquanto que estamos construindo as skills básicas d resolver problema não precisa, a menos que vocês queiram um desafio mensal mais difícil, que realmente demore o mês todo para resolver

o primeiro desafio mensal já resolveram no mesmo dia
; 1; ; 0;
0 '; 0';
BastterCode semana 10 - Antes late do que never - 94. Binary Tree Inorder Traversal - #15 de 17
oxe  
em 31/03/2023 14:46
@Giovanni

Você tava aprendendo JS, né? Lembro vagamente de você participando nessa linguagem.

Saca o canal desse cara aqui. Quando o YT me indicou, achei que era um cara normal e tal, mas o cara faz bruxaria. Depois descobri que ele é um game dev antigão, trabalhou com títulos AAA, era responsável pela otimização do código. Depois virou engenheiro do Google e agora tá com esse canal de JS sei lá por quê, acho que só pra se divertir. 

; 3; ; 0;
0 '; 0';
BastterCode semana 10 - Antes late do que never - 94. Binary Tree Inorder Traversal - #16 de 17
Giovanni  
em 03/04/2023 08:40
@oxe

muito maneiro !
; 1; ; 0;
0 '; 0';
BastterCode semana 10 - Antes late do que never - 94. Binary Tree Inorder Traversal - #17 de 17

5 usuários comentaram este tópico.
Clique para ir para o primeiro comentário do usuário.

Ações Pesquisa Videos Livros Análise de Carteira Desconto FAQs Orientação Esportiva Ofertas e Serviços Bastter System Boletim IR Podcasts Revista Tecnologia - Ajuda Eu Assinar Ações Pesquisa Videos Livros Análise de Carteira Desconto FAQs Ofertas e Serviços Orientação Esportiva Boletim BS Podcasts IR Tecnologia Ajuda eu Revista Assinar Assinar

BastterZap