ARTES #016

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 016

este es el articulo 16

Pregunta sobre el algoritmo del algoritmo

Hice dos preguntas esta semana, ambas relacionadas con cálculos de árboles binarios y se implementaron mediante recursividad e iteración respectivamente.

226. Invertir árbol binario voltear árbol binario

Dificultad: Fácil

Invertir un árbol binario.

Ejemplo:

Entrada:

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

Salida:

 4

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

Curiosidades: Este problema fue inspirado por:

Google: el 90% de nuestros ingenieros usan el software que tú escribiste (Homebrew), pero no puedes invertir un árbol binario en una pizarra, así que vete a la mierda.

Solución

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.Suma de ruta

Dificultad de la pregunta: Fácil

Dado un árbol binario y una suma objetivo, determine si hay una ruta desde el nodo raíz hasta el nodo hoja en el árbol. La suma de todos los valores de los nodos en esta ruta es igual a la suma objetivo.

Descripción: Los nodos hoja se refieren a nodos que no tienen nodos secundarios.

Ejemplo: Dado el siguiente árbol binario, así como el objetivo y sum = 22,

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

Devuelve true porque hay una ruta 5->4->11->2 desde el nodo raíz hasta el nodo hoja con suma objetivo 22.

Solución

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

Revisión

Reseña como artículo solo:

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

CONSEJOS

• Diferentes significados de NULL, nil, Nil NSNull

  bandera	valor	significado
  NULO	(nulo *)0	El valor cero literal de un puntero C
  nulo	(identificación)0	El valor cero literal de un objeto Objective-C
  Nulo	(Clase)0	El valor cero literal de una clase Objective-C
  NSNulo	[NSNull nulo]	Un único objeto utilizado para representar un valor cero.

  Referencia: https://nshipster.cn/nil/

• Para facilitar la traducción, utilicé Youdao SDK para crear una herramienta de traducción. La entrada es un archivo de texto y la salida también es un archivo de texto, que se traduce segmento por segmento. Ver también:

  https://github.com/dandan2009/youdaoTranslate

Compartir

Como desarrollador de iOS, ¿cómo aprender Java para poder leer la cuarta edición del algoritmo? ¿Cómo configurar un entorno de desarrollo Java?