ARTES #016

ARTS é uma atividade iniciada por 由左耳朵耗子--陈皓: Faça pelo menos uma pergunta sobre o algoritmo leetcode toda semana, leia e comente pelo menos um artigo técnico em inglês, aprenda pelo menos uma habilidade técnica e compartilhe um artigo com opiniões e pensamentos. (Ou seja, Algoritmo, Revisão, Dica e Compartilhamento são chamados de ARTS) e persistem por pelo menos um ano.

ARTES 016

Este é o artigo 16

Pergunta sobre algoritmo de algoritmo

Fiz duas perguntas esta semana, ambas relacionadas a cálculos de árvores binárias, e foram implementadas usando recursão e iteração respectivamente.

226. Inverter árvore binária inverter árvore binária

Dificuldade: Fácil

Inverta uma árvore binária.

Exemplo:

Entrada:

     4
   /   \
  2     7
 / \   / \
1   3 6   9```

Saída:

 4

/
7 2 / \ /
9 6 3 1```

Curiosidades: Este problema foi inspirado por:

Google: 90% dos nossos engenheiros usam o software que você escreveu (Homebrew), mas você não pode inverter uma árvore binária em um quadro branco, então vá se foder.

Solução

Idioma: C

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* invertTree(struct TreeNode* root) {
    
}

//递归 rcursive
struct TreeNode* invertTree_1(struct TreeNode* root) {
    if (root == NULL) {
        return root;
    }
    if(root->left != NULL || root->right != NULL){
        struct TreeNode *temp = root->left;
        root->left  = root->right;
        root->right = temp;
    }
    if(root->left)
        invertTree(root->left);
    if(root->right)
        invertTree(root->right);
    return root;
}

//迭代 iteratively
struct TreeNode* invertTree(struct TreeNode* root) {
    if (root == NULL) {
        return root;
    }
    
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * (1000));

    int stackCount = 0;
    struct TreeNode* p = root;
    while (p) {
        if (p->right) {
            stack[stackCount++] = p->right;
        }
        
        if (p->left || p->right) {
            struct TreeNode *temp = p->left;
            p->left  = p->right;
            p->right = temp;
        }
        
        p = p->right;
        if (!p && stackCount >0) {
            p = stack[--stackCount];
        }
    }
    return root;
}

112.Soma do caminho

Dificuldade da pergunta: Fácil

Dada uma árvore binária e uma soma alvo, determine se existe um caminho do nó raiz até o nó folha na árvore. A soma de todos os valores dos nós neste caminho é igual à soma alvo.

Descrição: Nós folha referem-se a nós que não possuem nós filhos.

Exemplo: Dada a seguinte árvore binária, bem como o alvo e sum = 22,

              **5**
             / \
            **4 **  8
           /   / \
          **11 ** 13  4
         /  \      \
        7    **2**      1

Retorna true porque existe um caminho 5->4->11->2 do nó raiz até o nó folha com soma alvo 22.

Solução

Idioma: C

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool hasPathSum(struct TreeNode* root, int sum) {
    
}

//递归 rcursive
bool hasPathSum_1(struct TreeNode* root, int sum) {
    if (!root) {
        return false;
    }
    
    if (root->left || root->right) {
        return (hasPathSum(root->left,sum - root->val) || hasPathSum(root->right,sum - root->val));
    }
    return root->val == sum;
}

//迭代 iteratively
bool hasPathSum(struct TreeNode* root, int sum) {

    if (root == NULL) {
        return root;
    }
    
    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * (1000));
    int * sumStack = (int *)malloc(sizeof(int *) * (1000));
    int stackCount = 0;
    
    stack[stackCount]=root;
    sumStack[stackCount] = sum - root->val;
    stackCount++;
    while (stackCount >0) {
        stackCount--;
        struct TreeNode* p = stack[stackCount];
        int leftsum = sumStack[stackCount];
        
        printf("leftsum:%d",leftsum);
        if (!p->left && !p->right && leftsum==0) {
            return true;
        }
        
        if (p->left) {
            stack[stackCount]=p->left;
            sumStack[stackCount] = leftsum - p->left->val;
            stackCount++;
        }
        
        if (p->right) {
            stack[stackCount]=p->right;
            sumStack[stackCount] = leftsum - p->right->val;
            stackCount++;
        }
    }
    return false;
}

Revisão

Revisão apenas como um artigo:

https://dandan2009.github.io/2018/11/22/data-structures-diving-into-data-structures-part1/

DICAS

• Diferentes significados de NULL, nulo, Nil NSNull

  bandeira	valor	significado
  NULO	(vazio *)0	O valor literal zero de um ponteiro C
  nada	(id)0	O valor literal zero de um objeto Objective-C
  Nada	(Classe)0	O valor literal zero de uma classe Objective-C
  NSNulo	[NSNull nulo]	Um único objeto usado para representar um valor zero

  Referência: https://nshipster.cn/nil/

• Para facilitar a tradução, utilizei o Youdao SDK para fazer uma ferramenta de tradução. A entrada é um arquivo de texto e a saída também é um arquivo de texto, que é traduzido segmento por segmento. Veja também:

  https://github.com/dandan2009/youdaoTranslate

Compartilhar

Como desenvolvedor iOS, como aprender Java para ler a quarta edição do algoritmo? Como configurar um ambiente de desenvolvimento java?