Quarantadue record di deduzioni di algoritmi [101. Albero binario simmetrico, 100. Albero identico, 572. Sottoalbero di un altro albero]

L'algoritmo si sforza di dedurre quarantadue record di domande [101. Albero binario simmetrico, 100. Albero identico, 572. Sottoalbero di un altro albero]

2024-07-12

Prefazione

Nel capitolo Albero binario, inizia a praticare il funzionamento degli alberi binari.
Record 42 [101. Albero binario simmetrico].
Continua.

1. Lettura dell'argomento

Fornisci il nodo radice radice di un albero binario, Controlla se è assialmente simmetrico。

Esempio 1:
Inserisci qui la descrizione dell'immagine

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

Esempio 2:
Inserisci qui la descrizione dell'immagine

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

suggerimento:

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

Avanzato: puoi usareRicorsione e iterazioneDue modi per risolvere questo problema?

2. Prova a realizzare

Idea 1

Prova prima a usare la ricorsione. Nucleo: quali sono i criteri per giudicare la simmetria assiale?

Ricorsione: chiama te stesso.Nessuna logica duplicata trovata ancora：

Determinare sinistra==destra? L'immissione del sottoalbero non è corretta.
Il sottoalbero sinistro va a sinistra, al centro, e il sottoalbero destro va a destra, sinistra, al centro. Le sequenze sono uguali? Ma questo vale per l'intero albero. Anche l'inserimento del sottoalbero è sbagliato.

Idea 2

Utilizzare un approccio iterativo al cambiamento. Utilizzare l'attraversamento dell'ordine di livello.
Dopo aver ottenuto il risultato della sequenza degli strati, si valuta che ogni strato sia un numero pari e uguale dopo l'inverso. Ma per l'esempio due, questo non è vero perché il puntatore nullo è escluso.
L'idea non funziona.

Riassumere:Anche se sappiamo che dobbiamo cercare la simmetria, non disponiamo di uno standard unificato per giudicare la simmetria.。

3. Idee di riferimento

Collegamento di riferimento

Contenuto didattico

Simmetria assiale: i sottoalberi sinistro e destro del nodo radice possono essere invertiti per essere uguali? , come confrontare?
Ottenuto dalla spiegazioneIdea corretta: Questo attraversamento richiede il sottoalbero sinistro del nodo radice e il sottoalbero destro del nodo radice.Attraversare contemporaneamente . Solo attraversando due sottoalberi contemporaneamente possiamo giudicare se i nodi su entrambi i lati sono uguali.
- Per prima cosa, passa la sinistra del sottoalbero sinistro e la destra del sottoalbero destro. A questo punto, i nodi esterni vengono giudicati uguali;
- Quindi passare la destra del sottoalbero sinistro e la sinistra del sottoalbero destro. A questo punto, i nodi interni vengono giudicati uguali;
- Dopo entrambi i risultati, sono entrambi veri allo stesso tempo, indicando simmetria.
Determinare l'ordine di attraversamento: sinistra, destra, centro. Dopo aver elaborato il figlio sinistro, elabora nuovamente il figlio destro e restituisce il risultato al nodo centrale.
Cercando di implementareInadeguatezza delle idee : elabora solo il sottoalbero sinistro del nodo radice e trova che l'ordine del sottoalbero destro del nodo radice è diverso dal sottoalbero sinistro. Non è possibile ottenere una logica unificata invertendo l'ordine di attraversamento o altro.

Implementazione ricorsiva

Ogni commento è un'idea.

/**
 * 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

L'ordine trasversale di un albero (sottoalbero sinistro) è centro-sinistra, mentre l'ordine trasversale di un albero (sottoalbero destro) è centro-destra-sinistra.

Idea iterativa 1

Elabora simultaneamente il sottoalbero sinistro del nodo radice e il sottoalbero destro del nodo radice. È diverso dalla traversata precedente.
Usa la struttura della coda: putI due nodi da confrontare vengono messi in coda contemporaneamente,AncoraTiralo fuori allo stesso tempo . Determina se i due nodi estratti possono essere capovolti. Quindi, se i bambini di sinistra e di destra sono liberi, devono essere messi in coda anche loro.
Usa la struttura dello stack: è comunque necessario elaborare due nodi contemporaneamente. Ci sono due oggetti da confrontare.Inseriscilo allo stesso tempo ed estrailo allo stesso tempo。

Implementazione iterativa [struttura della coda]

La struttura dello stack è la stessa.

/**
 * 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

Riepilogo [Albero binario assialsimmetrico]:

È ancora trasversale, ma la differenza è:Entrambi gli alberi secondari devono essere attraversati contemporaneamente . Non è corretto ricorrere in profondità in qualsiasi sottoalbero.
Le condizioni per confrontare gli oggetti per determinare vero: entrambi sono vuoti o i valori sono uguali. Il resto è falso.
Inoltre, non è possibile attraversare ricorsivamente alcun sottoalbero, poiché l'ordine dei lati sinistro e destro è diverso.
Non è un attraversamento dell'ordine di livello. Se devi attraversare gli strati in sequenza: ottieni i risultati di ogni strato e inverti per vedere se sono uguali. Come segue (non consigliato), le risposte sopra sono tutte molto buone.

/**
 * 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

Pratica delle domande

【100.Stesso albero】

1. Titolo

Dati i nodi radice p e q di due alberi binari, scrivi una funzione per verificare se i due alberi sono uguali.

Se due alberiStrutturalmente sono uguali e i nodi hanno gli stessi valori, sono considerati uguali.

Esempio 1:

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

Esempio 2:

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

Esempio 3:

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

suggerimento:

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

Idee

Determina se due alberi sono uguali. La struttura è la stessa e i valori sono gli stessi.

Allora deveSolo quando vengono elaborati due alberi contemporaneamente può esserci un oggetto di confronto. . È inutile solo attraversare/effettuare qualsiasi operazione su un albero.
Differenze da [101. Albero binario simmetrico], oggetti di confronto.QuiIl bambino sinistro dell'oggetto di confronto viene confrontato con il bambino sinistro; il bambino destro viene confrontato con il bambino destro . Vengono forniti i parametri per la chiamata ricorsiva.

Codice

/**
 * 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.Sottoalbero di un altro albero】

argomento

Ti vengono dati due alberi binari root e subroot.Controlla se root contiene e subRoot haStessa struttura e valori dei nodi sottoalbero. Se presente restituisce vero; altrimenti restituisce falso.

Un sottoalbero di un albero binario include un nodo dell'albero e tutti i nodi discendenti di questo nodo. l'albero può anche essere visto come un sottoalbero di se stesso.

Esempio 1:

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

Esempio 2:

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

suggerimento:

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

Idee

(1) Anche i sottoalberi giudicano uguali due alberi. È possibile utilizzare [100. Implementazione del codice delle domande] per risolvere il giudizio di uguaglianza.
(2) Ma deve essere trovato nella radiceUguale al valore del nodo radice subRoot nodo come nodo radice del sottoalbero. Attraversa la radice utilizzando l'ordine dei livelli.

Codice

/**
 * 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

Riepilogo del testo completo

Nucleo: attraversare due alberi contemporaneamente per determinare l'oggetto di confronto. Eseguire l'implementazione ricorsiva.

Nessun attraversamento profondo dell'albero produrrà un confronto tra entrambi i lati dell'oggetto.

(La correzione è gradita, si prega di indicare la fonte in caso di ristampa)

Condivisione della tecnologia

L'algoritmo si sforza di dedurre quarantadue record di domande [101. Albero binario simmetrico, 100. Albero identico, 572. Sottoalbero di un altro albero]

Prefazione

1. Lettura dell'argomento

2. Prova a realizzare

Idea 1

Idea 2

3. Idee di riferimento

Contenuto didattico

Implementazione ricorsiva

Idea iterativa 1

Implementazione iterativa [struttura della coda]

Riepilogo [Albero binario assialsimmetrico]:

Pratica delle domande

【100.Stesso albero】

1. Titolo

Idee

Codice

【572.Sottoalbero di un altro albero】

argomento

Idee

Codice

Riepilogo del testo completo

Profilo personale

le mie informazioni di contatto