Quarenta e dois registros de deduções de algoritmos [101. Árvore binária simétrica, 100. Árvore idêntica, 572. Subárvore de outra árvore]

O algoritmo se esforça para deduzir quarenta e dois registros de questões [101. Árvore binária simétrica, 100. Árvore idêntica, 572. Subárvore de outra árvore]

2024-07-12

Prefácio

No capítulo Árvore Binária, comece a praticar a operação de árvores binárias.
Registro 42 [101. Árvore binária simétrica].
continuar.

1. Leitura do tópico

Fornece o nó raiz raiz de uma árvore binária, Verifique se é axialmente simétrico。

Exemplo 1:
Insira a descrição da imagem aqui

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

Exemplo 2:
Insira a descrição da imagem aqui

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

dica:

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

Avançado: você pode usarRecursão e iteraçãoDuas maneiras de resolver esse problema?

2. Tente perceber

Ideia 1

Tente usar a recursão primeiro. Núcleo: Quais são os critérios para julgar a simetria axial?

Recursão: ligue para você mesmo.Nenhuma lógica duplicada encontrada ainda：

Determinar esquerda==direita? A inserção da subárvore está incorreta.
A subárvore esquerda vai para a esquerda, centro, e a subárvore direita vai para a direita, esquerda, centro. As sequências são iguais? Mas isso é para a árvore inteira. Entrar na subárvore também está errado.

Ideia 2

Use uma abordagem iterativa para mudar. Use travessia de ordem de nível.
Após obter o resultado da sequência de camadas, considera-se que cada camada é um número par e igual após o inverso. Mas, por exemplo, isso não é verdade porque o ponteiro nulo foi excluído.
A ideia não funciona.

Resumir:Embora saibamos que precisamos de procurar simetria, não temos um padrão unificado para julgar a simetria.。

3. Ideias de referência

Link de referência

Conteúdo de aprendizagem

Simetria axial: as subárvores esquerda e direita do nó raiz podem ser invertidas para serem iguais? , como comparar?
Obtido da explicaçãoIdéia correta: esta travessia requer a subárvore esquerda do nó raiz e a subárvore direita do nó raiz.Atravessar simultaneamente . Somente percorrendo duas subárvores ao mesmo tempo podemos julgar se os nós de ambos os lados são iguais.
- Primeiro, passe à esquerda da subárvore esquerda e à direita da subárvore direita. Neste momento, os nós externos são considerados iguais;
- Em seguida, passe pela direita da subárvore esquerda e pela esquerda da subárvore direita. Neste momento, os nós internos são considerados iguais;
- Após ambos os retornos, ambos são verdadeiros ao mesmo tempo, indicando simetria.
Determine a ordem de passagem: esquerda, direita, centro. Depois de processar o filho esquerdo, processe o filho direito novamente e retorne o resultado ao nó do meio.
Tentando implementarInadequação de ideias : processe apenas a subárvore esquerda do nó raiz e descubra que a ordem da subárvore direita do nó raiz é diferente da subárvore esquerda. Você não pode obter lógica unificada invertendo a ordem de passagem ou algo assim.

Implementação recursiva

Cada comentário é uma ideia.

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

A ordem de deslocamento de uma árvore (subárvore esquerda) é centro-esquerda, e a ordem de deslocamento de uma árvore (subárvore direita) é centro-direita-esquerda.

Ideia iterativa 1

Processe a subárvore esquerda do nó raiz e a subárvore direita do nó raiz simultaneamente. É diferente da travessia anterior.
Use estrutura de fila: putOs dois nós a serem comparados são colocados na fila ao mesmo tempo,De novoRetire ao mesmo tempo . Determine se os dois nós extraídos podem ser invertidos. Portanto, se as crianças da esquerda e da direita estiverem livres, elas também precisam ser colocadas na fila.
Use estrutura de pilha: ainda precisa processar dois nós ao mesmo tempo. Existem dois objetos para comparar.Coloque-o ao mesmo tempo e retire-o ao mesmo tempo。

Implementação iterativa [estrutura de fila]

A estrutura da pilha é a mesma.

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

Resumo [Árvore Binária Axisimétrica]:

Ainda é uma travessia, mas a diferença é:Ambas as subárvores devem ser percorridas simultaneamente . Não é correto recorrer profundamente a qualquer subárvore.
As condições para comparar objetos para determinar verdadeiro: ambos estão vazios ou os valores são iguais; O resto é falso.
Também não é possível percorrer recursivamente qualquer subárvore, porque a ordem dos lados esquerdo e direito é diferente.
Não é uma travessia de ordem de nível. Se você tiver que percorrer o nível sequencialmente: obtenha os resultados de cada nível, inverta e verifique se eles são iguais. Como segue (não recomendado), as respostas acima são todas muito boas.

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

Prática de perguntas

【100.Mesma árvore】

1. Título

Dados os nós raiz p e q de duas árvores binárias, escreva uma função para testar se as duas árvores são iguais.

Se duas árvoresEstruturalmente iguais e os nós têm os mesmos valores, eles são considerados iguais.

Exemplo 1:

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

Exemplo 2:

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

Exemplo 3:

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

dica:

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

Ideias

Determine se duas árvores são iguais. A estrutura é a mesma e os valores são os mesmos.

Então deveSomente quando duas árvores são processadas ao mesmo tempo pode haver um objeto de comparação. . É inútil apenas percorrer/fazer qualquer operação em uma árvore.
Diferenças de [101. Árvore Binária Simétrica], objetos de comparação.aquiO filho esquerdo do objeto de comparação é comparado com o filho esquerdo; o filho direito é comparado com o filho direito; . Os parâmetros para a chamada recursiva são fornecidos.

Código

/**
 * 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.Subárvore de outra árvore】

tema

Você recebe duas árvores binárias raiz e subRoot.Verifique se root contém e subRoot possuiMesma estrutura e valores de nó subárvore. Se presente, retorna verdadeiro; caso contrário, retorna falso.

Uma subárvore de uma árvore binária inclui um nó da árvore e todos os nós descendentes deste nó. A árvore também pode ser vista como uma subárvore de si mesma.

Exemplo 1:

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

Exemplo 2:

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

dica:

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

Ideias

(1) As subárvores também consideram duas árvores iguais. Você pode usar [100. Implementação do código de perguntas] para resolver o julgamento de igualdade.
(2) Mas deve ser encontrado na raizIgual ao valor do nó raiz subRoot nó como o nó raiz da subárvore. Percorra a raiz usando ordem de nível.

Código

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

Resumo do texto completo

Núcleo: Atravesse duas árvores ao mesmo tempo para determinar o objeto de comparação. Execute a implementação recursiva.

Nenhuma travessia mais profunda da árvore produzirá uma comparação de ambos os lados do objeto.

(Correção bem-vinda, indique a fonte ao reimprimir)

Compartilhamento de tecnologia

O algoritmo se esforça para deduzir quarenta e dois registros de questões [101. Árvore binária simétrica, 100. Árvore idêntica, 572. Subárvore de outra árvore]

Prefácio

1. Leitura do tópico

2. Tente perceber

Ideia 1

Ideia 2

3. Ideias de referência

Conteúdo de aprendizagem

Implementação recursiva

Ideia iterativa 1

Implementação iterativa [estrutura de fila]

Resumo [Árvore Binária Axisimétrica]:

Prática de perguntas

【100.Mesma árvore】

1. Título

Ideias

Código

【572.Subárvore de outra árvore】

tema

Ideias

Código

Resumo do texto completo

Perfil pessoal

minhas informações de contato