Partage de technologie

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

Préface

Dans le chapitre Arbre binaire, commencez à pratiquer le fonctionnement des arbres binaires.
Enregistrement 42 [101. Arbre binaire symétrique].
continuer.

---

1. Lecture du sujet

Donnez-vous la racine du nœud racine d'un arbre binaire, Vérifiez s'il est axialement symétrique。

Exemple 1:

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

Exemple 2 :

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

indice:

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

Avancé : vous pouvez utiliserRécursivité et itérationDeux façons de résoudre ce problème ?

---

2. Essayez de réaliser

Idée 1

Essayez d'abord d'utiliser la récursivité. Noyau : Quels sont les critères pour juger de la symétrie axiale ?

Récursion : appelez-vous.Aucune logique en double trouvée pour l'instant：

• Déterminer gauche == droite ? La saisie du sous-arbre est incorrecte.
• Le sous-arbre de gauche va à gauche, au centre et le sous-arbre de droite va à droite, à gauche, au centre. Les séquences sont-elles égales ? Mais c'est pour l'arbre entier. La saisie du sous-arbre est également erronée.

Idée 2

Utilisez une approche itérative du changement. Utilisez le parcours par ordre de niveau.
Après avoir obtenu le résultat de la séquence de couches, il est jugé que chaque couche est un nombre pair et égal après inversion. Mais pour le deuxième exemple, ce n'est pas vrai car le pointeur nul est exclu.
L'idée ne fonctionne pas.

Résumer:Même si nous savons que nous devons rechercher la symétrie, nous n’avons pas de norme unifiée pour juger de la symétrie.。

---

3. Idées de référence

Lien de référence

Contenu d'apprentissage

• Symétrie axiale : les sous-arbres gauche et droit du nœud racine peuvent-ils être inversés pour être égaux ? , comment comparer ?
• Obtenu à partir de l'explicationIdée correcte: Ce parcours nécessite le sous-arbre gauche du nœud racine et le sous-arbre droit du nœud racine.Traverser simultanément . Ce n’est qu’en parcourant deux sous-arbres à la fois que nous pouvons juger si les nœuds des deux côtés sont égaux.
  • Tout d'abord, passez la gauche du sous-arbre gauche et la droite du sous-arbre droit. À ce stade, les nœuds externes sont jugés égaux ;
  • Passez ensuite la droite du sous-arbre gauche et la gauche du sous-arbre droit. A ce moment, les nœuds internes sont jugés égaux ;
  • Après les deux retours, ils sont tous deux vrais en même temps, indiquant une symétrie.
• Déterminez l’ordre de parcours : gauche, droite, centre. Après avoir traité l'enfant de gauche, traitez à nouveau l'enfant de droite et renvoyez le résultat au nœud du milieu.
• Essayer de mettre en œuvreInadéquation des idées : Traitez uniquement le sous-arbre gauche du nœud racine et constatez que l'ordre du sous-arbre droit du nœud racine est différent de celui du sous-arbre gauche. Vous ne pouvez pas obtenir une logique unifiée en inversant l'ordre de parcours, ou autre.

Implémentation récursive

Chaque commentaire est une idée.

/**
 * 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'ordre de parcours d'un arbre (sous-arbre gauche) est centre-gauche et l'ordre de parcours d'un arbre (sous-arbre droit) est centre-droite-gauche.

Idée itérative 1

• Traitez simultanément le sous-arbre gauche du nœud racine et le sous-arbre droit du nœud racine. C’est différent du parcours précédent.
• Utiliser la structure de file d'attente : putLes deux nœuds à comparer sont mis dans la file d'attente en même temps,EncoreSortez-le en même temps . Déterminez si les deux nœuds extraits peuvent être inversés. Ainsi, si les enfants de gauche et de droite sont libres, il faut également les mettre dans la file d'attente.
• Utiliser la structure de pile : il faut toujours traiter deux nœuds en même temps. Il y a deux objets à comparer.Mettez-le en même temps et retirez-le en même temps。

Implémentation itérative [structure de file d'attente]

La structure de la pile est la même.

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

---

Résumé [Arbre binaire axisymétrique] :

• Il s'agit toujours d'une traversée, mais la différence est :Les deux sous-arbres doivent être parcourus simultanément . Il n’est pas correct de récurer profondément dans un sous-arbre.
• Les conditions de comparaison des objets pour déterminer vrai : les deux sont vides ou les valeurs sont égales. Le reste est faux.
• Il n'est pas non plus possible de parcourir de manière récursive un sous-arbre, car l'ordre des côtés gauche et droit est différent.
• Il ne s’agit pas d’un parcours par ordre de niveau. Si vous devez parcourir le niveau de manière séquentielle : récupérez les résultats de chaque niveau, inversez puis vérifiez s'ils sont égaux. Comme suit (non recommandé), les réponses ci-dessus sont toutes très bonnes.

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

---

Pratique des questions

【100.Même arbre】

1. Titre

Étant donné les nœuds racines p et q de deux arbres binaires, écrivez une fonction pour tester si les deux arbres sont identiques.

Si deux arbresStructurellement identique et les nœuds ont les mêmes valeurs, ils sont considérés comme identiques.

Exemple 1:

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

Exemple 2 :

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

Exemple 3 :

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

indice:

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

Idées

Déterminez si deux arbres sont identiques. La structure est la même et les valeurs sont les mêmes.

• Alors il fautCe n'est que lorsque deux arbres sont traités en même temps qu'il peut y avoir un objet de comparaison. . Il est inutile de parcourir/effectuer une opération uniquement en profondeur sur un arbre.
• Différences avec [101. Arbre binaire symétrique], objets de comparaison.iciL'enfant de gauche de l'objet de comparaison est comparé à l'enfant de gauche ; l'enfant de droite est comparé à l'enfant de droite ; . Les paramètres de l'appel récursif sont donnés.

Code

/**
 * 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.Sous-arbre d'un autre arbre】

sujet

Vous disposez de deux arbres binaires racine et sous-racine.Vérifiez si root contient et subRoot aMêmes valeurs de structure et de nœud sous-arbre. S'il est présent, renvoie vrai ; sinon, renvoie faux.

Un sous-arbre d'un arbre binaire comprend un nœud de l'arbre et tous les nœuds descendants de ce nœud. L'arbre peut également être considéré comme un sous-arbre de lui-même.

Exemple 1:

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

Exemple 2 :

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

indice:

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

Idées

(1) Les sous-arbres jugent également que deux arbres sont égaux. Vous pouvez utiliser [100. Question Code Implementation] pour résoudre le jugement d'égalité.
(2) Mais il faut le trouver à la racineÉgal à la valeur du nœud racine subRoot node comme nœud racine du sous-arbre. Parcourez la racine en utilisant l'ordre des niveaux.

Code

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

---

Résumé en texte intégral

Noyau : parcourez deux arbres en même temps pour déterminer l'objet de comparaison. Effectuer une implémentation récursive.

Aucune traversée d'arbre plus profonde ne produira une comparaison des deux côtés de l'objet.

(Correction bienvenue, merci d'indiquer la source lors de la réimpression)