2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Beginnen Sie im Kapitel „Binärbäume“ mit dem Üben der Funktionsweise von Binärbäumen.
Datensatz 42 [101. Symmetrischer Binärbaum].
weitermachen.
Geben Sie den Wurzelknoten eines Binärbaums an. Prüfen Sie, ob es axialsymmetrisch ist。
Beispiel 1:
输入：root = [1,2,2,3,4,4,3]
输出：true
Beispiel 2:
输入：root = [1,2,2,null,3,null,3]
输出：false
Hinweis:
树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100
Erweitert: Sie können verwendenRekursion und IterationZwei Möglichkeiten, dieses Problem zu lösen?
Versuchen Sie es zunächst mit der Rekursion. Kern: Was sind die Kriterien zur Beurteilung der Achsensymmetrie?
Rekursion: Rufen Sie sich selbst an.Es wurde noch keine doppelte Logik gefunden：
Verwenden Sie einen iterativen Ansatz für Veränderungen. Verwenden Sie die Durchquerung der Ebenenreihenfolge.
Nach Erhalt des Ergebnisses der Schichtfolge wird beurteilt, dass jede Schicht eine gerade Zahl ist und nach der Umkehrung gleich ist. Aber zum Beispiel zwei ist dies nicht wahr, da der Nullzeiger ausgeschlossen ist.
Die Idee funktioniert nicht.
Zusammenfassen:Obwohl wir wissen, dass wir nach Symmetrie suchen müssen, haben wir keinen einheitlichen Standard zur Beurteilung der Symmetrie.。
Jeder Kommentar ist eine Idee.
/**
* 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);
}
};
Die Durchlaufreihenfolge eines Baums (linker Teilbaum) ist links-zentriert, und die Durchlaufreihenfolge eines Baums (rechter Teilbaum) ist rechts-links-zentriert.
Die Stapelstruktur ist dieselbe.
/**
* 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;
}
};
Schreiben Sie anhand der Wurzelknoten p und q zweier Binärbäume eine Funktion, um zu testen, ob die beiden Bäume gleich sind.
Wenn zwei BäumeStrukturell gleich und die Knoten haben die gleichen Werte, sie gelten als gleich.
Beispiel 1:
输入：p = [1,2,3], q = [1,2,3]
输出：true
Beispiel 2:
输入：p = [1,2], q = [1,null,2]
输出：false
Beispiel 3:
输入：p = [1,2,1], q = [1,1,2]
输出：false
Hinweis:
两棵树上的节点数目都在范围 [0, 100] 内
-10^4 <= Node.val <= 10^4
Bestimmen Sie, ob zwei Bäume gleich sind. Der Aufbau ist gleich und die Werte sind gleich.
/**
* 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;
}
};
Sie erhalten zwei Binärbäume, Root und SubRoot.Überprüfen Sie, ob root enthält und subRoot hatGleiche Struktur und gleiche Knotenwerte Teilbaum. Wenn vorhanden, wird „true“ zurückgegeben; andernfalls wird „false“ zurückgegeben.
Ein Teilbaum eines Binärbaums umfasst einen Knoten des Baums und alle untergeordneten Knoten dieses Knotens. Baum kann auch als Teilbaum von sich selbst betrachtet werden.
Beispiel 1:
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
Beispiel 2:
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false
Hinweis:
root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-10^4 <= root.val <= 10^4
-10^4 <= subRoot.val <= 10^4
(1) Teilbäume beurteilen auch zwei Bäume als gleich. Sie können [100. Question Code Implementation] verwenden, um das Gleichheitsurteil zu lösen.
(2) Aber es muss in der Wurzel gefunden werdenEntspricht dem Wert des subRoot-Wurzelknotens Knoten als Wurzelknoten des Teilbaums. Durchqueren Sie die Wurzel in der Reihenfolge der Ebenen.
/**
* 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;
}
};
Kern: Durchqueren Sie zwei Bäume gleichzeitig, um das Vergleichsobjekt zu bestimmen. Führen Sie eine rekursive Implementierung durch.
Keine tiefere Baumdurchquerung führt zu einem Vergleich beider Seiten des Objekts.
(Korrektur erwünscht, bitte beim Nachdruck die Quelle angeben)
Er widmet sich seit mehr als 30 Jahren der Technologieforschung und beherrscht verschiedene Sprachen wie Java, Linux, Javascript, PHP, CSS usw. Er hat viele Beiträge im Open-Source-Bereich geleistet Entwicklerdokumentationsstation, um einige Themen in der Technologieentwicklung als zukünftige Referenz zu teilen
