моя контактная информация
Почтамезофия@protonmail.com
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
В главе «Двоичное дерево» начните практиковаться в работе с двоичными деревьями.
Запись 42 [101. Симметричное двоичное дерево].
продолжать.
Дайте вам корень корневого узла двоичного дерева, Проверьте, является ли он осесимметричным.。
Пример 1:
输入：root = [1,2,2,3,4,4,3]
输出：true
Пример 2:
输入：root = [1,2,2,null,3,null,3]
输出：false
намекать:
树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100
Расширенный: Вы можете использоватьРекурсия и итерацияДва способа решения этой проблемы?
Попробуйте сначала использовать рекурсию. Core: Каковы критерии оценки осевой симметрии?
Рекурсия: позвоните себе.Повторяющаяся логика пока не найдена：
Используйте итеративный подход к изменениям. Используйте обход по уровням.
После получения результата последовательности слоев определяется, что каждый слой имеет четное число и равен после обратного преобразования. Но, например, во-вторых, это неверно, поскольку нулевой указатель исключен.
Идея не работает.
Подведем итог:Хотя мы знаем, что нам нужно искать симметрию, у нас нет единого стандарта для оценки симметрии.。
Каждый комментарий — это идея.
/**
* 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);
}
};
Порядок обхода дерева (левое поддерево) — лево-центр, а порядок обхода дерева (правое поддерево) — право-лево-центр.
Структура стека такая же.
/**
* 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;
}
};
Учитывая корневые узлы p и q двух двоичных деревьев, напишите функцию, проверяющую, одинаковы ли эти два дерева.
Если два дереваСтруктурно одинаковые и узлы имеют одинаковые значения, они считаются одинаковыми.
Пример 1:
输入：p = [1,2,3], q = [1,2,3]
输出：true
Пример 2:
输入：p = [1,2], q = [1,null,2]
输出：false
Пример 3:
输入：p = [1,2,1], q = [1,1,2]
输出：false
намекать:
两棵树上的节点数目都在范围 [0, 100] 内
-10^4 <= Node.val <= 10^4
Определите, одинаковы ли два дерева. Структура та же самая и ценности те же.
/**
* 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;
}
};
Вам даны два корня и подкорень двоичных деревьев.Проверьте, содержит ли root и имеет ли subRootТа же структура и значения узлов поддерево. Если присутствует, возвращает true; в противном случае возвращает false.
Поддерево бинарного дерева включает в себя узел дерева и все узлы-потомки этого узла. дерево также можно рассматривать как поддерево самого себя.
Пример 1:
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
Пример 2:
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false
намекать:
root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-10^4 <= root.val <= 10^4
-10^4 <= subRoot.val <= 10^4
(1) Поддеревья также считают два дерева равными. Вы можете использовать [100. Реализация кода вопроса] для решения проблемы равенства.
(2)Но его надо найти в корнеРавен значению корневого узла subRoot. node как корневой узел поддерева. Пройдите корень, используя порядок уровней.
/**
* 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;
}
};
Ядро: одновременное перемещение двух деревьев для определения объекта сравнения. Выполните рекурсивную реализацию.
Никакой глубокий обход дерева не даст сравнения обеих сторон объекта.
(Исправление приветствуется, при перепечатке указывайте источник)
Он посвятил себя исследованию технологий более 30 лет и владеет различными языками, такими как Java, Linux, Javascript, php, css и т. д. Он внес большой вклад в область открытого исходного кода. Станция документации для разработчиков, где можно поделиться некоторыми проблемами в разработке технологий для дальнейшего использования. Все ознакомьтесь.
Почтамезофия@protonmail.com