SENI #016

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 016

Ini adalah pasal 16

Pertanyaan algoritma algoritma

Saya mengerjakan dua pertanyaan minggu ini, keduanya terkait dengan penghitungan pohon biner, dan diimplementasikan masing-masing menggunakan rekursi dan iterasi.

226. Balikkan Pohon Biner, balikkan pohon biner

Kesulitan: Mudah

Balikkan pohon biner.

Contoh:

Masukan:

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

Keluaran:

 4

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

Hal-hal sepele: Permasalahan ini terinspirasi oleh :

Google: 90% teknisi kami menggunakan perangkat lunak yang Anda tulis (Homebrew), tetapi Anda tidak dapat membalikkan pohon biner di papan tulis, jadi pergilah.

Solusi

Bahasa: 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.Jumlah Jalur

Kesulitan Pertanyaan: Mudah

Diberikan pohon biner dan jumlah target, tentukan apakah terdapat jalur dari simpul akar ke simpul daun di pohon. Jumlah seluruh nilai node pada jalur ini sama dengan jumlah target.

Deskripsi: Node daun mengacu pada node yang tidak memiliki node turunan.

Contoh: Mengingat pohon biner berikut, serta target dan sum = 22,

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

Mengembalikan true karena terdapat jalur 5->4->11->2 dari simpul akar ke simpul daun dengan jumlah target 22.

Solusi

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

Ulasan

Tinjau sebagai artikel saja:

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

TIPS

• Arti berbeda dari NULL, nil, Nil NSNull

  bendera	nilai	artinya
  BATAL	(batal *)0	Nilai nol literal dari penunjuk C
  nihil	(id)0	Nilai nol literal dari objek Objective-C
  nihil	(Kelas)0	Nilai nol literal dari kelas Objective-C
  NSBatal	[NSNull nol]	Sebuah objek tunggal yang digunakan untuk mewakili nilai nol

  Referensi: https://nshipster.cn/nil/

*Untuk memudahkan terjemahan, saya menggunakan Youdao SDK untuk membuat alat terjemahan. Inputnya berupa file teks, dan outputnya juga berupa file teks, yang diterjemahkan segmen demi segmen. Lihat juga:

https://github.com/dandan2009/youdaoTranslate

Bagikan

Sebagai pengembang iOS, bagaimana cara mempelajari Java untuk membaca algoritma edisi keempat? Bagaimana cara mengatur lingkungan pengembangan java?