Mi informacion de contacto
Correo[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
En el capítulo Árbol binario, comience a practicar el funcionamiento de árboles binarios.
Registro 42 [101. Árbol binario simétrico].
continuar.
Darle la raíz del nodo raíz de un árbol binario, Compruebe si es axialmente simétrico.。
Ejemplo 1:
输入：root = [1,2,2,3,4,4,3]
输出：true
Ejemplo 2:
输入：root = [1,2,2,null,3,null,3]
输出：false
pista:
树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100
Avanzado: Puedes usarRecursión e iteración¿Dos formas de resolver este problema?
Intente usar la recursividad primero. Núcleo: ¿Cuáles son los criterios para juzgar la simetría axial?
Recursión: llámate a ti mismo.Aún no se ha encontrado ninguna lógica duplicada：
Utilice un enfoque iterativo para el cambio. Utilice recorrido de orden de nivel.
Después de obtener el resultado de la secuencia de capas, se considera que cada capa es un número par e igual después de la inversa. Pero en el ejemplo dos, esto no es cierto porque el puntero nulo está excluido.
La idea no funciona.
Resumir:Aunque sabemos que debemos buscar la simetría, no tenemos un estándar unificado para juzgar la simetría.。
Cada comentario es una 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);
}
};
El orden transversal de un árbol (subárbol izquierdo) es de centro izquierda y el orden transversal de un árbol (subárbol derecho) es de centro derecha-izquierda.
La estructura de la pila es la misma.
/**
* 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;
}
};
/**
* 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;
}
};
Dados los nodos raíz p y q de dos árboles binarios, escriba una función para probar si los dos árboles son iguales.
si dos arbolesEstructuralmente igual y los nodos tienen los mismos valores., se consideran iguales.
Ejemplo 1:
输入：p = [1,2,3], q = [1,2,3]
输出：true
Ejemplo 2:
输入：p = [1,2], q = [1,null,2]
输出：false
Ejemplo 3:
输入：p = [1,2,1], q = [1,1,2]
输出：false
pista:
两棵树上的节点数目都在范围 [0, 100] 内
-10^4 <= Node.val <= 10^4
Determina si dos árboles son iguales. La estructura es la misma y los valores son los mismos.
/**
* 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;
}
};
Se le proporcionan dos árboles binarios, raíz y subraíz.Compruebe si la raíz contiene y la subRoot tieneMisma estructura y valores de nodo. subárbol. Si está presente, devuelve verdadero; en caso contrario, devuelve falso.
Un subárbol de un árbol binario incluye un nodo del árbol y todos los nodos descendientes de este nodo. El árbol también puede verse como un subárbol de sí mismo.
Ejemplo 1:
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
Ejemplo 2:
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false
pista:
root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-10^4 <= root.val <= 10^4
-10^4 <= subRoot.val <= 10^4
(1) Los subárboles también consideran que dos árboles son iguales. Puede utilizar [100.Implementación del código de preguntas] para resolver el juicio de igualdad.
(2) Pero debe encontrarse en la raíz.Igual al valor del nodo raíz subRoot nodo como nodo raíz del subárbol. Atraviesa la raíz usando el orden de niveles.
/**
* 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;
}
};
Núcleo: atraviesa dos árboles al mismo tiempo para determinar el objeto de comparación. Realizar implementación recursiva.
Ningún recorrido de árbol más profundo producirá una comparación de ambos lados del objeto.
(Corrección bienvenida, indique la fuente al reimprimir)
Se ha dedicado a la investigación de tecnología durante más de 30 años y domina varios lenguajes como java, linux, javascript, php, css, etc. Ha realizado muchas contribuciones en el campo del código abierto. Estación de documentación para desarrolladores para compartir algunos problemas en el desarrollo de tecnología para referencia futura.
Correo[email protected]