내 연락처 정보
우편메소피아@프로톤메일.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
고급: 사용할 수 있습니다.재귀와 반복이 문제를 해결하는 두 가지 방법은 무엇입니까?
먼저 재귀를 사용해 보세요. 핵심: 축 대칭을 판단하는 기준은 무엇입니까?
재귀: 자신에게 전화하세요.아직 중복된 로직이 발견되지 않았습니다.：
변경하려면 반복적인 접근 방식을 사용하세요. 레벨 순서 순회를 사용합니다.
레이어 시퀀스 결과를 얻은 후 각 레이어는 역순으로 짝수이고 동일한 것으로 판단됩니다. 그러나 두 번째 예에서는 널 포인터가 제외되기 때문에 이는 사실이 아닙니다.
아이디어가 작동하지 않습니다.
요약하다:우리는 대칭을 찾아야 한다는 것을 알고 있지만 대칭을 판단하는 통일된 표준은 없습니다.。
모든 댓글은 아이디어입니다.
/**
* 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;
}
};
두 개의 이진 트리 루트와 하위 루트가 제공됩니다.루트에 포함되어 있고 하위 루트에 포함되어 있는지 확인하십시오.동일한 구조 및 노드 값 하위 트리. 존재하는 경우 true를 반환하고, 그렇지 않으면 false를 반환합니다.
이진 트리의 하위 트리에는 트리의 노드와 이 노드의 모든 하위 노드가 포함됩니다. tree는 자신의 하위 트리로 볼 수도 있습니다.
예시 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) 하지만 루트에서 찾아야 합니다.하위 루트 루트 노드 값과 동일 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;
}
};
Core: 두 개의 트리를 동시에 탐색하여 비교 대상을 결정합니다. 재귀적 구현을 수행합니다.
더 깊은 트리 순회에서는 객체의 양쪽을 비교할 수 없습니다.
(수정가능하며, 재배포시 출처를 꼭 밝혀주세요)
그는 30년 이상 기술 연구에 전념해 왔으며, java, linux, javascript, php, css 등 다양한 언어에 능숙하며, 오픈 소스 분야에 많은 공헌을 했습니다. 나중에 참조할 수 있도록 기술 개발의 일부 문제를 공유하는 개발자 문서 스테이션입니다.
우편메소피아@프로톤메일.com