ARTES #017

ARTES es una actividad iniciada por 由左耳朵耗子--陈皓: Haga al menos una pregunta sobre el algoritmo leetcode cada semana, lea y comente al menos un artículo técnico en inglés, aprenda al menos una habilidad técnica y comparta un artículo con opiniones y pensamientos. (Es decir, Algoritmo, Revisión, Sugerencia y Compartir se denominan ARTS) y persisten durante al menos un año.

##ARTES 017

este es el articulo 17

Pregunta sobre el algoritmo del algoritmo

222. Contar nodos de árbol completos

Dificultad de la pregunta: Mediana

Dado un árbol binario completo, cuente el número de nodos.

Nota:

<u style=“display: inline;”>Definición de un árbol binario completo de :</u> En un árbol binario completo, todos los niveles, excepto posiblemente el último, están completamente llenos y todos los nodos del último nivel están lo más a la izquierda posible. Puede tener entre 1 y 2 nodos^h inclusive en el último nivel h.

Ejemplo:

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

**Output:** 6```



#### Solución

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

El algoritmo anterior ha agotado el tiempo de espera. Vi las soluciones de otras personas de la siguiente manera:

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

De hecho, los dos algoritmos anteriores son recursivos, pero el algoritmo uno se agota, pero el algoritmo dos es normal y el tiempo de ejecución es de solo 12 ms. No entiendo por qué la condición if (root->val!=INT_MAX) es útil. Esta condición es definitivamente cierta. ¿Por qué se puede aprobar el caso de prueba de LeetCode si se agrega esta condición, pero expirará si no se agrega? ?

Método 3: usar iteración

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

Esto también expirará. De hecho, los métodos uno y tres son recorridos de árboles binarios, pero todos expirarán aquí.

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

Aunque este algoritmo también utiliza recursividad, utiliza las características de un árbol binario completo. Es muy sencillo calcular el número de nodos de un árbol binario completo.

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 también aprovecha las características de un árbol binario completo. Si comprende el código en la parte del comentario, comprenderá todo el algoritmo.

Revisión

Ver también: https://dandan2009.github.io/2018/11/27/data-structures-part2-a-quick-comparison/

CONSEJOS

Entiende la estática nuevamente.

Las siguientes variables se declaran en un método de una clase:

static int x;

Suponga que el nombre de la clase es A y luego cree una instancia de los objetos de A: a1, a2. En este momento la variable

Aunque este es un punto de conocimiento muy antiguo, es posible que cometa errores de cálculo accidentalmente al usar estática y es difícil solucionar el problema, por lo que debe pensar con claridad antes de usar estática.

Compartir

Google Cloud es gratuito durante un año: https://cloud.google.com/free/ Al registrarse, debe tener una tarjeta de crédito en moneda extranjera, como una tarjeta Visa. Para evitar registros maliciosos, Google deducirá un dólar de la tarjeta de crédito al registrarse, pero lo reembolsará después de un tiempo.

https://github.com/tracyone/v2ray.fun compartido con un clic v2ray

https://233yes.com/post/1/ Instalación infalible