資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的同構樹
假設我們有兩個二叉樹；我們必須定義一個函式來檢查它們是否相同。我們知道，當二叉樹在結構上相同且節點的值相同時，它們被認為是相同的。
因此，如果輸入類似於 [1,2,3],[1,2,3]，那麼輸出將為 True
為了解決這一問題，我們將遵循以下步驟 -
定義一個名為 isSameTree 的函式，它將採用兩個樹節點 p 和 q
如果 p 與 NULL 相同且 q 與 NULL 相同，則 -
返回 true
如果 p 與 NULL 相同或 q 與 NULL 相同，則 -
返回 false
如果 p 的 val 與 p 的 val 相同，且 isSameTree(p 的 left，q 的 left) 為 true，且 isSameTree(p 的 right，q 的 right) 為 true，則
返回 true
返回 false
示例
讓我們看以下實現以獲得更好的理解 -
#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 isSameTree(TreeNode *p, TreeNode* q){
if (p == NULL && q == NULL)
return true;
if (p == NULL || q == NULL)
return false;
if (p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right))
return true;
return false;
}
};
main(){
Solution ob;
vector<int> v = {1,2,3}, v1 = {1,2,3};
TreeNode *root1 = make_tree(v);
TreeNode *root2 = make_tree(v1);
cout << (ob.isSameTree(root1, root2));
}輸入
{1,2,3}, {1,2,3}輸出
1
更新日期：2020 年 6 月 10 日
326 次瀏覽
廣告