2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Aloita binääripuiden toiminnan harjoittelu luvussa Binaaripuu.
Tietue 42 [101.
jatkaa.
Anna sinulle binääripuun juurisolmun juuri, Tarkista, onko se aksiaalisesti symmetrinen。
Esimerkki 1:
输入：root = [1,2,2,3,4,4,3]
输出：true
Esimerkki 2:
输入：root = [1,2,2,null,3,null,3]
输出：false
vihje:
树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100
Edistynyt: Voit käyttääRekursio ja iteraatioKaksi tapaa ratkaista tämä ongelma?
Kokeile ensin rekursiota. Ydin: Mitkä ovat kriteerit aksiaalisen symmetrian arvioinnissa?
Rekursio: Soita itsellesi.Päällekkäistä logiikkaa ei vielä löytynyt：
Käytä iteratiivista lähestymistapaa muutokseen. Käytä tasotilauksen läpikulkua.
Kerrossekvenssituloksen saamisen jälkeen päätellään, että jokainen kerros on parillinen luku ja yhtä suuri käänteisenä. Mutta esimerkiksi kaksi, tämä ei ole totta, koska nollaosoitin on poissuljettu.
Idea ei toimi.
Yhteenveto:Vaikka tiedämme, että meidän on etsittävä symmetriaa, meillä ei ole yhtenäistä standardia symmetrian arvioimiseksi.。
Jokainen kommentti on 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);
}
};
Puun läpikulkujärjestys (vasen alipuu) on vasen-keski ja puun (oikea alipuu) läpikulkujärjestys on oikea-vasen-keski.
Pinorakenne on sama.
/**
* 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;
}
};
Kun on annettu kahden binaaripuun juurisolmut p ja q, kirjoita funktio testataksesi, ovatko nämä kaksi puuta samat.
Jos kaksi puutaRakenteellisesti sama ja solmuilla on samat arvot, niitä pidetään samanlaisina.
Esimerkki 1:
输入：p = [1,2,3], q = [1,2,3]
输出：true
Esimerkki 2:
输入：p = [1,2], q = [1,null,2]
输出：false
Esimerkki 3:
输入：p = [1,2,1], q = [1,1,2]
输出：false
vihje:
两棵树上的节点数目都在范围 [0, 100] 内
-10^4 <= Node.val <= 10^4
Selvitä, ovatko kaksi puuta samanlaisia. Rakenne on sama ja arvot ovat samat.
/**
* 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;
}
};
Sinulle annetaan kaksi binaaripuuta juuri ja alijuuri.Tarkista sisältääkö root ja subRoot onSama rakenne ja solmuarvot alipuu. Jos läsnä, palauttaa tosi, muussa tapauksessa palauttaa epätosi.
Binääripuun alipuu sisältää puun solmun ja kaikki tämän solmun jälkeläiset solmut. puuta voidaan pitää myös alipuuna itsestään.
Esimerkki 1:
输入：root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true
Esimerkki 2:
输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false
vihje:
root 树上的节点数量范围是 [1, 2000]
subRoot 树上的节点数量范围是 [1, 1000]
-10^4 <= root.val <= 10^4
-10^4 <= subRoot.val <= 10^4
(1) Alipuut arvioivat myös kaksi puuta samanarvoisiksi. Voit käyttää [100 Question Code Implementation] ratkaistaksesi tasa-arvopäätöksen.
(2) Mutta se on löydettävä juurestaSama kuin alijuuren juurisolmun arvo solmu alipuun juurisolmuna. Läpi juuren läpi tasojärjestyksen mukaan.
/**
* 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;
}
};
Ydin: Selaa kahta puuta samanaikaisesti määrittääksesi vertailuobjektin. Suorita rekursiivinen toteutus.
Mikään syvempi puun läpikulku ei tuota vertailua kohteen molemmista puolista.
(Oikaisu on tervetullut, ilmoita lähde uusintapainoksessa)
Hän on omistautunut teknologian tutkimukselle yli 30 vuoden ajan ja hallitsee useita kieliä, kuten java, linux, javascript, php, css jne. Hän on tehnyt paljon työtä avoimen lähdekoodin alalla Kehittäjän dokumentaatioasema jakaaksesi joitain teknologian kehittämisen ongelmia tulevaa käyttöä varten
