資料結構
網路
關係資料庫管理系統 (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
廣告