C++ 中的反转子树
假设我们有两棵二叉树，分别称为源树和目标树;我们必须检查源树是否存在某个反转树 T，使得它是目标树的子树。因此，这意味着目标节点中存在一个节点，其值和结构与 T 节点(包括其所有后代节点)完全相同。
众所周知，如果满足以下任一条件，则称一棵树是另一棵树的反转:
两棵树均为空
其左右子节点可以随意交换，并且其左右子树是反转的。
因此，如果输入与源节点类似
目标节点
则输出为 True
为了解决这个问题，我们将按照以下步骤 −
定义一个函数 check()，它将接受 node1、node2，
如果 node1 和 node2 都为 null，则 −
返回 true
如果 node1 或 node2 中任何一个为 null，则 −
返回 false
如果如果 node1 的值不等于 node2 的值，则 −
返回 false
op1 := check(node1 的左侧，node2 的左侧) and check(node1 的右侧，node2 的右侧)
op2 := check(node1 的右侧，node2 的左侧) and check(node1 的左侧，node2 的右侧)
当 op1 和 op2 中至少有一个为 true 时返回 true
定义一个函数 resolve()，该函数接受 source、target 参数
如果 source 和 target 为空，则 −
返回 true
如果 source 或 target 中任意一个为 null，则 −
返回 false
op1 := check(target, source)
如果 op1 为 true，则 −
返回 true
当 resolve(source, target 左侧) 或 resolve(source, target 右侧) 中至少一个为 true 时返回 true
让我们看看下面的实现以便更好地理解 −
示例
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) {
val = data;
left = NULL;
right = NULL;
}
};
class Solution {
public:
bool check(TreeNode* node1, TreeNode* node2){
if(!node1 && !node2)
return true;
if(!node1 || !node2)
return false;
if(node1->val != node2->val) {
return false;
}
bool op1 = check(node1->left, node2->left) && check(node1->right, node2->right);
bool op2 = check(node1->right, node2->left) && check(node1->left, node2->right);
return op1 || op2;
}
bool solve(TreeNode* source, TreeNode* target) {
if(!target && !source)
return true;
if(!target || !source)
return false;
bool op1 = check(target, source);
if(op1)
return true;
return solve(source, target->left) || solve(source, target->right);
}
};
main(){
Solution ob;
TreeNode *target = new TreeNode(6);
target->left = new TreeNode(3);
target->right = new TreeNode(1);
target->right->left = new TreeNode(3);
target->right->right = new TreeNode(2);
target->right->right->left = new TreeNode(4);
TreeNode *source = new TreeNode(1);
source->left = new TreeNode(2);
source->right = new TreeNode(3);
source->left->right = new TreeNode(4);
cout << (ob.solve(source, target));
}
输入
TreeNode *target = new TreeNode(6); target->left = new TreeNode(3); target->right = new TreeNode(1); target->right->left = new TreeNode(3); target->right->right = new TreeNode(2); target->right->right->left = new TreeNode(4); TreeNode *source = new TreeNode(1); source->left = new TreeNode(2); source->right = new TreeNode(3); source->left->right = new TreeNode(4);
输出
1
