SENI #017

SENI adalah kegiatan yang diprakarsai oleh 由左耳朵耗子--陈皓: Kerjakan setidaknya satu pertanyaan algoritma leetcode setiap minggu, baca dan komentari setidaknya satu artikel teknis berbahasa Inggris, pelajari setidaknya satu keterampilan teknis, dan bagikan artikel yang berisi opini dan pemikiran. (Artinya, Algoritma, Review, Tip, dan Share disebut sebagai SENI) dan bertahan setidaknya selama satu tahun.

SENI 017

Ini adalah pasal 17

Pertanyaan algoritma algoritma

222. Hitung Node Pohon Lengkap

Tingkat Kesulitan Soal: Sedang

Diberikan pohon biner lengkap, hitung jumlah node.

Catatan:

<u style=“display: inline;”>Definisi pohon biner lengkap dari :</u> Dalam pohon biner lengkap, setiap level, kecuali mungkin level terakhir, terisi penuh, dan semua node pada level terakhir berada sejauh mungkin di kiri. Ia dapat memiliki antara 1 dan 2^h node inklusif pada level h terakhir.

Contoh:

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

**Output:** 6```



#### Solusi

Bahasa: **C**

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

Metode 1, rekursif:

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

Algoritme di atas telah habis waktunya. Saya melihat solusi orang lain sebagai berikut:

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

Faktanya, kedua algoritma di atas sama-sama rekursif, tetapi algoritma satu kali habis, tetapi algoritma dua normal, dan waktu berjalan hanya 12ms. Saya tidak mengerti mengapa kondisi if (root->val!=INT_MAX) berguna. Kondisi ini pasti ada benarnya. Mengapa test case LeetCode dapat dilewati jika kondisi ini ditambahkan, tetapi akan habis waktu jika tidak ditambahkan? ?

Metode 3: Gunakan iterasi

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

Waktu ini juga akan habis. Faktanya, metode satu dan tiga adalah penjelajahan pohon biner, tetapi metode tersebut akan selalu ada di sini.

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

Meskipun algoritma ini juga menggunakan rekursi, namun menggunakan karakteristik pohon biner lengkap. Sangat mudah untuk menghitung jumlah node untuk pohon biner penuh.

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

Algoritma ini juga memanfaatkan karakteristik pohon biner yang lengkap. Jika Anda memahami kode di bagian komentar, Anda akan memahami keseluruhan algoritma.

Ulasan

Lihat juga: https://dandan2009.github.io/2018/11/27/data-structures-part2-a-quick-comparison/

TIPS

Pahami statis lagi.

Variabel berikut dideklarasikan dalam suatu metode di kelas:

static int x;

Asumsikan nama kelasnya adalah A, lalu buat instance objek A: a1, a2. Saat ini, variabelnya

Meskipun ini adalah poin pengetahuan yang sangat lama, Anda mungkin membuat kesalahan perhitungan secara tidak sengaja saat menggunakan statis, dan sulit untuk memecahkan masalah, jadi Anda harus berpikir jernih sebelum menggunakan statis.

Bagikan

Google Cloud gratis selama satu tahun: https://cloud.google.com/free/ Saat mendaftar, Anda harus memiliki kartu kredit mata uang asing, seperti kartu visa. Untuk mencegah pendaftaran jahat, Google akan memotong satu dolar dari kartu kredit saat mendaftar, tetapi akan mengembalikannya setelah beberapa saat.

https://github.com/tracyone/v2ray.fun membagikan v2ray sekali klik

https://233yes.com/post/1/ Instalasi anti bodoh