BastterCode semana 10 - Antes late do que never - 94. Binary Tree Inorder Traversal
comentada em 03/04/2023 08:40

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;
      
  }
}

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...

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

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;
    }
};?

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;
    }
};?

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;
    }
};?

@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.

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

@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.

@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

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.

@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.