ARTES #017

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 017

Este é o artigo 17

Pergunta sobre algoritmo de algoritmo

222. Contar nós de árvore completos

Dificuldade da pergunta: Média

Dada uma árvore binária completa, conte o número de nós.

Nota:

<u style=“display: inline;”>Definição de uma árvore binária completa de:</u> Em uma árvore binária completa, todos os níveis, exceto possivelmente o último, são completamente preenchidos e todos os nós do último nível estão o mais à esquerda possível. Pode ter entre 1 e 2 nós^h inclusive no último nível h.

Exemplo:

**Input:** 
    1
   / \
  2   3
 / \  /
4  5 6

**Output:** 6```



#### Solução

Idioma: **C**

```c
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

Método 1, recursivo:

int countNodes(struct TreeNode* root) {
        if (!root) {
        return 0;
    }

    int count = 1;
    if (root->left) {
        count +=countNodes(root->left);
    }
    if (root->right) {
        count +=countNodes(root->right);
    }
}

O algoritmo acima expirou. Vi as soluções de outras pessoas da seguinte forma:

Método 2:

int countNodes(struct TreeNode* root) {
    if(!root) return 0;
    if(root->val!=INT_MAX){
        root->val=INT_MAX;
        return 1+countNodes(root->left)+countNodes(root->right);
    }
    return -1111111;
}

Na verdade, os dois algoritmos acima são recursivos, mas o algoritmo um atinge o tempo limite, mas o algoritmo dois é normal e o tempo de execução é de apenas 12 ms. Não entendo por que a condição if (root->val!=INT_MAX) é útil. Esta condição é definitivamente verdadeira. Por que o caso de teste do LeetCode pode ser aprovado se esta condição for adicionada, mas atingirá o tempo limite se não for adicionada? ?

Método 3: Use iteração

int countNodes(struct TreeNode* root) {
    if (!root) {
        return 0;
    }
  struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * (1000));
    int count = 0;
    int index = 0;
    struct TreeNode* p= root;
    
    while (p) {
        ++count;
        printf("%d,%d=;;;;",count,p->val);
        if (p->right) {
            printf("ooooooo");
            stack[index++] = p->right;
        }
        
        p = p->left;
        
        if (!p && index > 0) {
            printf("kkkkkkkkkkk");
            p =  stack[--index];
        }
    }
    
    return count;
}

Isso também irá expirar. Na verdade, os métodos um e três são travessias de árvores binárias, mas todos eles terão tempo limite aqui.

Método 4:

int countNodes(struct TreeNode* root)
{
    /* get left depth and right depth */
    struct TreeNode *pL = root, *pR = root;
    int dep = 0;
    for(; pL && pR; dep++)
    {
        pL = pL->left;
        pR = pR->right;
    }
    
    /* count the full tree collectively */
    if(!pL && !pR) return (1<<dep) -1;
    
    /* count left and right sub-trees separately */
    return countNodes(root->left) + 1 + countNodes(root->right);
}

Embora este algoritmo também utilize recursão, ele utiliza as características de uma árvore binária completa. É muito simples calcular o número de nós de uma árvore binária completa.

Método 5

int height(struct TreeNode *root)
{
    int h;
    
    h = -1;
    while (root) {
        ++h;
        root = root->left;
    }
    return h;
}

int countNodes(struct TreeNode* root)
{
    int h1, h2;
    
    
    if (!root) return 0;
    
    h1 = height(root->left);
    h2 = height(root->right);
    
    if (h1 == h2) {
        //说明左子树是满树 (1 << (h1 + 1)) - 1) 是左子树节点的个数
        return 1 + ((1 << (h1 + 1)) - 1) + countNodes(root->right);
    } else {
         //说明右子树是满树 ，((1 << h1) - 1) 是右子树节点的个数
        return 1 + ((1 << h1) - 1) + countNodes(root->left);
    }
}

Este algoritmo também aproveita as características de uma árvore binária completa. Se você entender o código na parte de comentários, entenderá todo o algoritmo.

Revisão

Veja também: https://dandan2009.github.io/2018/11/27/data-structures-part2-a-quick-comparison/

DICAS

Entenda a estática novamente.

As seguintes variáveis são declaradas em um método em uma classe:

static int x;

Suponha que o nome da classe seja A e então instancie os objetos de A: a1, a2. Neste momento, a variável

Embora este seja um ponto de conhecimento muito antigo, você pode cometer erros de cálculo acidentalmente ao usar estática e é difícil solucionar problemas, portanto, você deve pensar com clareza antes de usar estática.

Compartilhar

O Google Cloud é gratuito por um ano: https://cloud.google.com/free/ Ao se registrar, você deve ter um cartão de crédito em moeda estrangeira, como um cartão Visa. Para evitar registros maliciosos, o Google deduzirá um dólar do cartão de crédito durante o registro, mas o reembolsará depois de um tempo.

https://github.com/tracyone/v2ray.fun compartilhou v2ray com um clique

https://233yes.com/post/1/ Instalação à prova de erros