Localizando o Valor na Última Linha à Esquerda

Para encontrar o valor mais à esquerda na última linha de uma árvore binária, podemos utilizar uma busca em profundidade (DFS) que prioriza a exploração do lado esquerdo e rastreia a profundidade máxima alcançada.

class Solution {
public:
    int profundidadeAlvo = -1;
    int valorFinal;

    void buscarEsquerda(TreeNode* no, int nivel) {
        if (!no->left && !no->right) {
            if (nivel > profundidadeAlvo) {
                profundidadeAlvo = nivel;
                valorFinal = no->val;
            }
            return;
        }

        if (no->left) buscarEsquerda(no->left, nivel + 1);
        if (no->right) buscarEsquerda(no->right, nivel + 1);
    }

    int findBottomLeftValue(TreeNode* root) {
        buscarEsquerda(root, 0);
        return valorFinal;
    }
};

Verificação de Soma de Caminho

Este algoritmo verifica se existe um caminho da raiz até uma folha onde a soma dos valores dos nós é igual a um valor alvo. A abordagem mais eficiente utiliza a subtração do valor atual do total restante.

class Solution {
public:
    bool hasPathSum(TreeNode* node, int somaRestante) {
        if (!node) return false;
        
        // Verifica se é um nó folha
        if (!node->left && !node->right) {
            return somaRestante == node->val;
        }
        
        int novoAlvo = somaRestante - node->val;
        return hasPathSum(node->left, novoAlvo) || hasPathSum(node->right, novoAlvo);
    }
};

Recuperando Todos os Caminhos com Soma Específica

Diferente da verificação simples, aqui precisamos retornar todos os caminhos completos. Utilizamos backtracking para adicinoar e remover elementos de uma lista temporária conforme percorremos a árvore.

class Solution {
public:
    vector<vector>> todasAsRotas;
    
    void encontrarCaminhos(TreeNode* node, int alvo, vector<int>& atual) {
        if (!node) return;
        
        atual.push_back(node->val);
        
        if (!node->left && !node->right && alvo == node->val) {
            todasAsRotas.push_back(atual);
        } else {
            encontrarCaminhos(node->left, alvo - node->val, atual);
            encontrarCaminhos(node->right, alvo - node->val, atual);
        }
        
        atual.pop_back(); // Backtracking
    }

    vector<vector>> pathSum(TreeNode* root, int targetSum) {
        vector<int> caminhoTemporario;
        encontrarCaminhos(root, targetSum, caminhoTemporario);
        return todasAsRotas;
    }
};</int></vector></int></vector>

Construção de Árvore a partir de Travessias Inorder e Postorder

A reconstrução baseia-se no fato de que o último elemento da sequência postorder é sempre a raiz. Ao localizar essa raiz na sequência inorder, dividimos a árvore em subárvores esquerda e direita.

class Solution {
public:
    TreeNode* montarArvore(vector<int>& inorder, vector<int>& postorder) {
        if (postorder.empty()) return nullptr;

        int valorRaiz = postorder.back();
        TreeNode* raiz = new TreeNode(valorRaiz);

        if (postorder.size() == 1) return raiz;

        // Localiza divisor no Inorder
        int divisor = 0;
        for (; divisor < inorder.size(); divisor++) {
            if (inorder[divisor] == valorRaiz) break;
        }

        // Segmentação dos vetores
        vector<int> inEsq(inorder.begin(), inorder.begin() + divisor);
        vector<int> inDir(inorder.begin() + divisor + 1, inorder.end());

        postorder.pop_back();
        vector<int> postEsq(postorder.begin(), postorder.begin() + inEsq.size());
        vector<int> postDir(postorder.begin() + inEsq.size(), postorder.end());

        raiz->left = montarArvore(inEsq, postEsq);
        raiz->right = montarArvore(inDir, postDir);

        return raiz;
    }
};</int></int></int></int></int></int>

Construção de Árvore a partir de Travessias Preorder e Inorder

Similar ao método anterior, mas aqui a raiz é identificada no início da sequência preorder.

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty()) return nullptr;

        int topo = preorder[0];
        TreeNode* root = new TreeNode(topo);

        if (preorder.size() == 1) return root;

        int mid = 0;
        for (; mid < inorder.size(); mid++) {
            if (inorder[mid] == topo) break;
        }

        vector<int> inEsq(inorder.begin(), inorder.begin() + mid);
        vector<int> inDir(inorder.begin() + mid + 1, inorder.end());

        vector<int> preResto(preorder.begin() + 1, preorder.end());
        vector<int> preEsq(preResto.begin(), preResto.begin() + inEsq.size());
        vector<int> preDir(preResto.begin() + inEsq.size(), preResto.end());

        root->left = buildTree(preEsq, inEsq);
        root->right = buildTree(preDir, inDir);

        return root;
    }
};</int></int></int></int></int></int></int>