在 C++ 中翻转等价二叉树
c++server side programmingprogramming更新于 2025/4/15 10:07:17
假设我们有一棵二叉树。我们必须翻转这棵二叉树。翻转表示:选择任意节点，并交换左子树和右子树。现在，当且仅当我们能够在经过一定次数的翻转操作后从 X 生成 Y 时，二叉树 X 才与二叉树 Y 翻转等价。我们必须编写一个方法来确定两棵二叉树是否翻转等价。树由根节点 root1 和 root2 给出。因此，如果树是 −
如果我们翻转值为 1、3 和 5 的节点，则输出将为 true。
为了解决这个问题，我们将遵循以下步骤 −
定义一个递归函数solve()，这将需要两棵树t1和t2。
如果root1和root2为空，则返回true
否则，当root1为空或root2为空时，则返回false
否则，当(t1和t2都没有左子树)或(t1和t2都有左子树，且这两个节点的左子树的值相同)，则
return solve(left of root1, left of root2) and solve(right of root1, right of root2)
否则
return solve(left of root1, right of root2) and solve(right of root1, left of root2)
让我们看看下面的实现以便更好地理解 −
示例
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
}else{
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
}else{
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
class Solution {
public:
bool flipEquiv(TreeNode* root1, TreeNode* root2) {
if(!root1 && !root2)return true;
else if(!root1 || !root2)return false;
else if(root1->val != root2->val) return false;
else if((!root1->left && !root2->left) || (root1->left && root2->left && root1->left->val == root2- >left->val)){
return flipEquiv(root1->left, root2->left) && flipEquiv(root1->right, root2->right);
}else{
return flipEquiv(root1->left, root2->right) && flipEquiv(root1->right, root2->left);
}
}
};
main(){
vector<int> v = {1,2,3,4,5,6,NULL,NULL,NULL,7,8};
TreeNode *r1 = make_tree(v);
vector<int> v1 = {1,3,2,NULL,6,4,5,NULL,NULL,NULL,NULL,NULL,NULL,8,7};
TreeNode *r2 = make_tree(v);
Solution ob;
cout << (ob.flipEquiv(r1, r2));
}
输入
[1,2,3,4,5,6,null,null,null,7,8] [1,3,2,null,6,4,5,null,null,null,null,8,7]
输出
1
