BastterCode semana 18 - 100. Same Tree
comentada em 28/06/2023 21:34

Essa eu achei mais difícil que a maioria dos desafios de nível fácil que eu fiz até agora. Mas pode ser também que tenha alguma forma fácil de fazer que eu não conheça.

Eu criei dois vetores, um para cada linked list/tree, para rastrear os nodes por onde passei. A partir daí, a ideia era analisar elementos simétricos entre as árvores, para verificar se os valores eram diferentes ou se um dos elementos tinha caminho para a esquerda/direita, enquanto o outro não tinha.

Daí, usei uma função para fazer uma verificação inicial da raiz, se ela existe nas duas árvores e se os valores são iguais.

Depois, uma função para ir passando para os nodes mais à esquerda, fazendo os testes, até chegar no último node da esquerda.

E outra para percorrer de volta os vetores que acompanham os nodes até achar um elemento que, em ambas as árvores, tenha caminho à direita. A partir daí, o loop recomeça.

Ou seja, em resumo, percorro o caminho pela esquerda até o fim, retorno até achar caminho pela direita, entro nesse caminho da direita e percorro pela esquerda até o fim de novo, assim por diante. Enquanto faço isso, vou testando se os valores são iguais em ambas as árvores e se tem caminho dos dois lados em ambas as árvores.

O loop termina quando eu encontro alguma inconsistência que torna as árvores diferentes e, portanto, retorno falso. Ou quando eu percorro de volta os vetores até o começo, hipótese em que analisei todos os elementos de ambas as árvores sem encontrar inconsistência e, portanto, retorno verdadeiro.

Para conseguir lidar com o estado de análise "indefinido", usei um char em vez de boolean. O boolean só retorna verdadeiro (1) ou falso (0), não tem um estado intermediário que me permita interromper a análise na metade para continuar em outra função. Usando um char, eu ocupo o mesmo espaço do boolean na memória e consigo setar -1 como estado indefinido.

class Solution {
private:    
    const char initCheck(const TreeNode* p, const TreeNode* q) {
        if ((p == nullptr) ^ (q == nullptr))
            return 0;
        
        if (!(p || q))
            return 1;
        
        if (p->val != q->val)
            return 0;
        
        return -1;
    }
    
    const char checkLeft(vector<TreeNode*>& fst, vector<TreeNode*>& snd, unsigned short& i) {        
        while (fst[i]->left && snd[i]->left) {
            if ((fst[i]->right == nullptr) ^ (snd[i]->right == nullptr))
                return 0;
            
            fst.push_back(fst[i]->left);
            snd.push_back(snd[i]->left);
            
            fst[i]->left = nullptr;
            snd[i]->left = nullptr;            
            
            ++i;
            
            if (fst[i]->val != snd[i]->val)
                return 0;
        }
        
        if (((fst[i]->left == nullptr) ^ (snd[i]->left == nullptr)) || ((fst[i]->right == nullptr) ^ (snd[i]->right == nullptr)))
            return 0;
        
        return -1;
    }
    
    const char checkRight(vector<TreeNode*>& fst, vector<TreeNode*>& snd, unsigned short& i) {               
        while (!(fst[i]->right || snd[i]->right)) {
            if (i > 0) {
                --i;
                fst.pop_back();
                snd.pop_back(); 
            }                
            else
                return 1;
        }       
        
        fst.push_back(fst[i]->right);
        snd.push_back(snd[i]->right);
        
        fst[i]->right = nullptr;
        snd[i]->right = nullptr;
        
        ++i;
        
        if (fst[i]->val != snd[i]->val)
            return 0;
        
        return -1;            
    }
    
public:
    
    bool isSameTree(TreeNode* p, TreeNode* q) {
        char answer = -1;       
        
        answer = initCheck(p, q);            
        if (answer == 0 || answer == 1)
            return answer;
        
        vector<TreeNode*> fst{p};
        vector<TreeNode*> snd{q};
        
        unsigned short i = 0;
        
        while (answer == -1) {            
            answer = checkLeft(fst, snd, i);
            if (answer == 0 || answer == 1)
                return answer;
            
            answer = checkRight(fst, snd, i);
            if (answer == 0 || answer == 1)
                return answer;               
        }
        
        return 0;        
    }
};?

@oxe tenta com queue

A ideia é: first in, first out.

Coloque os roots na queue e vai lendo de 2 em 2. 

Sempre coloque na fila os pares:

left arvore1, left arvore2
righ arvore1, right arvore2

E compare-os. Se tiver alguma diferença, é pq as árvores não são idênticas.

Se não conseguir, dá uma olhada na minha solution (tenta fazer antes):

** SPOILER ALERT **

import "dart:collection";

class Solution {
  bool isSameTree(TreeNode? p, TreeNode? q) {
      final queue = Queue<TreeNode?>();
      
      queue.add(p);
      queue.add(q);
      
      
      while (!queue.isEmpty) {
         final el1 = queue.removeFirst();
         final el2 = queue.removeFirst();
         
         if (el1 == null && el2 == null) continue;
         if (el1 == null || el2 == null) return false;
         if (el1.val != el2.val) return false;
         
         queue.addLast(el1.left);
         queue.addLast(el2.left);
         queue.addLast(el1.right);
         queue.addLast(el2.right);      
      }      
      
      return true;
  }
}?

@FlyCavok

Boa! Amanhã tô pilhado de trabalho, mas quarta vou testar essa abordagem e aproveitar pra tentar fazer minha própria queue.

Consegui fazer com a queue. De começo tive dificuldade de entender a ideia, mas acabei acertando. Aí vi teu código e dei uma ajustada final. Ficou bem mais simples e legível assim.

Aproveitei pra estudar sobre templates também.

template<typename T>
class Queue {
private:
  
    struct queue {
        T val;
        queue* next;
        
        queue(): val(0), next(nullptr) {}
        queue(T x): val(x), next(nullptr) {}
        queue(T x, queue* nxt): val(x), next(nxt) {}
    };
    
    queue* head;
    queue* tail;
    
    unsigned short size = 0;
  
    void delNode() {
        queue* temp = head;
        tail->next = head->next;
        head = tail->next;
        delete temp;
      
        --size;
    }
    
public:
        
    void insert(const T& val) {
        if (size == 0) {
          tail = new queue();
          head = tail;
          head->val = val;
        }
        else {
          tail->next = new queue();
          tail = tail->next;
          tail->val = val;
          tail->next = head;
        }
      
        ++size;     
    }
    
    const T get_value() {
        if (size == 0)
          return nullptr;
      
        T val = head->val;
        
        delNode();
        
        return val;
    }
    
    const bool isEmpty(){
        return (size == 0);
    }
};

class Solution {
private:  
  
    Queue<TreeNode*> queue;   
  
public:            
  
    bool isSameTree(TreeNode* p, TreeNode* q) {   
        queue.insert(p);
        queue.insert(q);
        
        while (queue.isEmpty() == false) {
            TreeNode* first = queue.get_value();            
            TreeNode* second = queue.get_value();   
                      
            if ((first == nullptr) ^ (second == nullptr)) return false;
            if ((first == nullptr) && (second == nullptr)) continue;
            if (first->val != second->val) return false;
               
            queue.insert(first->left);
            queue.insert(second->left);  
            queue.insert(first->right);       
            queue.insert(second->right);
        }
            
        return true;
    }
};?

Hoje bateu na cabeça que dava para resolver usando stack também, já que não importa se é FIFO ou LIFO, só importa que eu olhe cada par ao mesmo tempo.

Implementei um stack numa classe própria, fiz as funções e tal, aí percebi que o stack é, sem tirar nem por, o vector do C++. Até o nome das funções da biblioteca do vector remete ao stack (pop, push, etc.).

Aí acabou ficando assim o código.

class Solution {  
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
      vector<TreeNode*> stack{};
      
      stack.push_back(p);
      stack.push_back(q);
      
      while (stack.size() > 0) {
        TreeNode* first = stack.back();
        stack.pop_back();
        
        TreeNode* second = stack.back();
        stack.pop_back();
        
        if ((first == nullptr) ^ (second == nullptr)) 
          return false;
        if ((first == nullptr) || (second == nullptr))
          continue;
        if (first->val != second->val)
          return false;
        
        stack.push_back(first->left);
        stack.push_back(second->left);
        
        stack.push_back(first->right);
        stack.push_back(second->right);
      }
      
      return true;
    }
};?