数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中的倒置子树
假设我们有两棵二叉树，称为源树和目标树；我们必须检查源树是否有一些反转 T 使其成为目标树的子树。这意味着目标树中存在一个节点，其值和结构与 T 完全相同，包括其所有后代。
众所周知，如果满足以下条件，则一棵树被称为另一棵树的反转：
两棵树都为空
它的左子树和右子树可以互换，并且它的左子树和右子树是反转的。
因此，如果输入类似于源树
目标树
那么输出将为 True
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 check()，它将接收节点1、节点2，
如果节点1和节点2都为空，则：
返回 true
如果节点1或节点2其中一个为空，则：
返回 false
如果节点1的值不等于节点2的值，则：
返回 false
op1 := check(节点1的左子树, 节点2的左子树) 并且 check(节点1的右子树, 节点2的右子树)
op2 := check(节点1的右子树, 节点2的左子树) 并且 check(节点1的左子树, 节点2的右子树)
当 op1 和 op2 中至少一个为真时返回 true
定义一个函数 solve()，它将接收源树、目标树，
如果源树和目标树为空，则：
返回 true
如果源树或目标树其中一个为空，则：
返回 false
op1 := check(目标树, 源树)
如果 op1 为真，则：
返回 true
当 solve(源树, 目标树的左子树) 或 solve(源树, 目标树的右子树) 中至少一个为真时返回 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
更新于：2020年9月2日
浏览量：120
广告