Berbagi teknologi

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Kata pengantar

Pada bab Pohon Biner, mulailah berlatih pengoperasian pohon biner.
Rekam 42 [101. Pohon Biner Simetris].
melanjutkan.

---

1. Topik Membaca

Memberi Anda akar simpul akar dari pohon biner, Periksa apakah simetris secara aksial。

Contoh 1:

输入：root = [1,2,2,3,4,4,3]
输出：true
1
2

Contoh 2:

输入：root = [1,2,2,null,3,null,3]
输出：false
1
2

petunjuk:

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100
1
2

Lanjutan: Anda dapat menggunakanRekursi dan iterasiDua cara untuk mengatasi masalah ini?

---

2. Cobalah untuk menyadari

Ide 1

Coba gunakan rekursi terlebih dahulu. Inti: Apa kriteria untuk menilai simetri aksial?

Rekursi: Panggil diri Anda sendiri.Belum ada logika duplikat yang ditemukan：

• Tentukan kiri==kanan? Memasukkan subpohon salah.
• Subpohon kiri menjadi kiri, tengah, dan subpohon kanan menjadi kanan, kiri, tengah. Apakah urutannya sama? Tapi itu untuk keseluruhan pohon. Memasukkan subtree juga salah.

Ide 2

Gunakan pendekatan berulang untuk berubah. Gunakan traversal pesanan tingkat.
Setelah diperoleh hasil urutan lapisan, dinilai bahwa setiap lapisan bernilai genap dan sama setelah dibalik. Tapi misalnya dua, ini tidak benar karena penunjuk nol dikecualikan.
Idenya tidak berhasil.

Meringkaskan:Meskipun kita tahu bahwa kita perlu mencari simetri, kita tidak memiliki standar terpadu untuk menilai simetri.。

---

3. Referensi ide

Tautan referensi

Konten Pembelajaran

• Simetri aksial: Bisakah subpohon kiri dan kanan dari simpul akar dibalik agar sama? , bagaimana cara membandingkannya?
• Diperoleh dari penjelasanide yang benar: Traversal ini memerlukan subpohon kiri dari simpul akar dan subpohon kanan dari simpul akar.Melintasi secara bersamaan . Hanya dengan melintasi dua subpohon sekaligus kita dapat menilai apakah node di kedua sisi sama.
  • Pertama, lewati bagian kiri subpohon kiri dan kanan subpohon kanan. Pada saat ini, simpul terluar dinilai sama;
  • Kemudian lewati subpohon kanan kiri dan kiri subpohon kanan. Pada saat ini, node dalam dinilai sama;
  • Setelah keduanya kembali, keduanya benar pada saat yang sama, menunjukkan simetri.
• Tentukan urutan traversal: kiri, kanan, tengah. Setelah memproses anak kiri, proses lagi anak kanan, dan kembalikan hasilnya ke node tengah.
• Mencoba menerapkanKetidakcukupan ide : Hanya proses subpohon kiri dari simpul akar, dan temukan bahwa urutan subpohon kanan dari simpul akar berbeda dengan subpohon kiri. Anda tidak bisa mendapatkan logika terpadu dengan membalik urutan traversal, atau apa pun.

Implementasi rekursif

Setiap komentar adalah sebuah ide.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool iscompare(TreeNode* left,TreeNode* right){ //两边同时遍历，所以两个参数。返回是否相等，用bool类型。
        //确定终止条件
        if(!left && !right) return true;    //同时为空，可以翻转
        else if(!left && right) return false; //一个空，一个不为空。肯定不等
        else if (!right && left) return false;//一个空，一个不为空。肯定不等
        else if(left->val != right->val) return false;//都不为空，但是值不等

        //都不为空，值相等。说明可以继续进行外侧比较、内侧比较，不用return。
        bool outside = iscompare(left->left,right->right);  //同时比较，解决了左右遍历顺序不一样
        bool inside = iscompare(left->right,right->left);
        return outside && inside;   //同时返回true。才能返回true
    }
    bool isSymmetric(TreeNode* root) {
        return iscompare(root->left,root->right);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

Urutan traversal suatu pohon (subpohon kiri) adalah kiri-tengah, dan urutan traversal suatu pohon (subpohon kanan) adalah kanan-kiri-tengah.

Ide berulang 1

• Memproses subpohon kiri dari simpul akar dan subpohon kanan dari simpul akar secara bersamaan. Berbeda dengan traversal sebelumnya.
• Gunakan struktur antrian: putKedua node yang akan dibandingkan dimasukkan ke dalam antrian pada waktu yang bersamaan,LagiKeluarkan pada saat yang bersamaan . Tentukan apakah kedua node yang diekstraksi dapat dibalik. Jadi kalau anak kiri dan kanan ada waktu luang, mereka juga perlu dimasukkan ke dalam antrian.
• Gunakan struktur tumpukan: masih perlu memproses dua node secara bersamaan. Ada dua objek untuk dibandingkan.Masukkan pada saat yang sama dan keluarkan pada saat yang bersamaan。

Implementasi berulang [struktur antrian]

Struktur tumpukannya sama.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return false;
        queue<TreeNode*> que;
        que.push(root->left);//放入左子树
        que.push(root->right);//放入右子树
        while(!que.empty()){
            TreeNode* left = que.front(); que.pop();//取出比较对象中的左节点
            TreeNode* right = que.front();que.pop();//取出比较对象中的右节点

            if(!left && !right){    //都是空节点
                continue;
            }else if(!left || !right || left->val != right->val){
                return false;
            }

            que.push(left->left);
            que.push(right->right);
            que.push(left->right);
            que.push(right->left);
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

---

Ringkasan [Pohon Biner Axisymmetric]:

• Masih traversal, bedanya:Kedua subpohon harus dilalui secara bersamaan . Tidaklah benar untuk mengulang jauh ke dalam subpohon mana pun.
• Syarat membandingkan objek untuk menentukan kebenarannya: keduanya kosong; atau nilainya sama. Sisanya salah.
• Juga tidak mungkin untuk melintasi subpohon mana pun secara rekursif, karena urutan sisi kiri dan kanan berbeda.
• Ini bukan traversal tingkat-urutan. Jika Anda harus melintasi level secara berurutan: dapatkan hasil setiap level, balikkan, lalu periksa apakah hasilnya sama. Sebagai berikut (tidak disarankan), jawaban di atas semuanya sangat bagus.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        vector<vector<int>> level;
        queue<TreeNode*> que;
        if(!root) return false;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> vec;
            while(size--){
                TreeNode* cur = que.front();que.pop();
                if(cur){ //不是空节点
                    que.push(cur->left);
                    que.push(cur->right);
                    vec.push_back(cur->val);
                }else{
                    vec.push_back(INT_MIN);//因为节点的值【-100,100】。用一个最小值代表空。
                }
            }
            level.push_back(vec);
        }
        //获得层序遍历。包含空。空的数值借助INT_MIN代替。
        for(int i = 1;i < level.size();i++){
            vector<int> temp = level[i];
            reverse(temp.begin(),temp.end());
            if(temp != level[i]){
                return false;
            }
        }
        return true;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

---

Latihan soal

【100.Pohon yang sama】

1. Judul

Mengingat simpul akar p dan q dari dua pohon biner, tulislah sebuah fungsi untuk menguji apakah kedua pohon tersebut sama.

Jika dua pohonSecara struktural sama dan node memiliki nilai yang sama, mereka dianggap sama.

Contoh 1:

输入：p = [1,2,3], q = [1,2,3]
输出：true
1
2

Contoh 2:

输入：p = [1,2], q = [1,null,2]
输出：false
1
2

Contoh 3:

输入：p = [1,2,1], q = [1,1,2]
输出：false
1
2

petunjuk:

两棵树上的节点数目都在范围 [0, 100] 内
-10^4 <= Node.val <= 10^4
1
2

Ide ide

Tentukan apakah dua pohon itu sama. Strukturnya sama dan nilainya sama.

• Maka itu harusHanya ketika dua pohon diproses pada saat yang sama barulah ada objek perbandingan. . Tidak ada gunanya hanya melintasi/melakukan operasi apa pun pada pohon.
• Perbedaan dari [101. Pohon Biner Simetris], objek perbandingan.Di SiniAnak kiri objek pembanding dibandingkan dengan anak kiri; anak kanan dibandingkan dengan anak kanan . Parameter untuk panggilan rekursif diberikan.

Kode

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p && !q) return true;  //传入节点同时为空，可以对应
        else if(!p && q) return false;//一个空，另一个不是空。不可能对应。
        else if(p && !q) return false;//一个空，另一个不是空。不可能对应。
        else if(p->val != q->val) return false;//值不等，不可能对应。

        bool leftchild = isSameTree(p->left,q->left); 
        bool rightchild = isSameTree(p->right,q->right);
        return leftchild && rightchild;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

【572.Subpohon dari pohon lain】

tema

Anda diberikan dua akar pohon biner dan subRoot.Periksa apakah root berisi dan subRoot memilikiStruktur dan nilai simpul yang sama subpohon. Jika ada, kembalikan nilai benar; jika tidak, kembalikan salah.

Subpohon dari pohon biner mencakup simpul dari pohon dan semua simpul turunan dari simpul tersebut. pohon juga dapat dipandang sebagai subpohon dari dirinya sendiri.

Contoh 1:

输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
1
2

Contoh 2:

输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false
1
2

petunjuk:

root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-10^4 <= root.val <= 10^4
-10^4 <= subRoot.val <= 10^4
1
2
3
4

Ide ide

(1) Subpohon juga menilai dua pohon sama. Anda dapat menggunakan [100. Implementasi Kode Pertanyaan] untuk menyelesaikan penilaian kesetaraan.
(2) Tetapi harus ditemukan akarnyaSama dengan nilai simpul akar subRoot simpul sebagai simpul akar dari subpohon. Lintasi akar menggunakan urutan tingkat.

Kode

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSame(TreeNode* rootnode,TreeNode* subRootnode){
        if(!rootnode && !subRootnode) return true;
        else if(!rootnode && subRootnode) return false;
        else if(rootnode && !subRootnode) return false;
        else if(rootnode->val != subRootnode->val) return false;

        bool leftchild = isSame(rootnode->left,subRootnode->left);
        bool rightchild = isSame(rootnode->right,subRootnode->right);
        return leftchild && rightchild;
    }
    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        //先找到和subRoot值相等的节点，才有可能相等。得遍历root找到和subRoot值相等的节点，可能作为子树的根节点

        //用层序遍历
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            while(size--){
                TreeNode* cur = que.front();que.pop();
                if(cur->val == subRoot->val){
                    bool subtree = isSame(cur,subRoot);
                    if(subtree) return true;
                }
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

---

Ringkasan teks lengkap

Inti: Lintasi dua pohon sekaligus untuk menentukan objek perbandingan. Lakukan implementasi rekursif.

Penelusuran pohon yang lebih dalam tidak akan menghasilkan perbandingan kedua sisi objek.

(Koreksi diperbolehkan, harap sebutkan sumbernya saat mencetak ulang)