資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法律學C++ 中合併兩個二叉樹的程式
假設我們有二叉樹，並考慮當我們把其中一棵樹覆蓋在另一棵樹上的時候，兩棵樹的一些節點重疊，而另一些節點重疊。我們必須把它們合併成一棵新的二叉樹。合併規則類似於，如果兩個節點重疊，則將節點值相加作為合併後節點的新值。否則，非空節點將用作新樹的節點。
因此，如果樹是 -
那麼輸出將是 -
要解決這個問題，我們將遵循以下步驟 -
- 方法是 solve()。這需要兩個樹節點 n1 和 n2。這類似於
- 如果 n1 為空，而 n2 為非空，則返回 n2，否則當 n2 為空，而 n1 為非空時，返回 n1，當兩者都為空時，返回 null
- n1 的值 := n1 的值 + n2 的值
- n1 的左子節點 := solve(n1 的左子節點，n2 的左子節點)
- n1 的右子節點 := solve(n1 的右子節點，n2 的右子節點)
- 返回 n1
讓我們看以下實現，以便更好地理解 -
示例
#include<bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int v){
val = v;
left = right = NULL;
}
};
void inord(TreeNode *root) {
if (root != NULL) {
inord(root->left);
cout << root->val << " ";
inord(root->right);
}
}
class Solution {
public:
TreeNode* solve(TreeNode* n1, TreeNode* n2) {
if(!n1 && n2)
return n2;
else if(!n2 && n1)
return n1;
else if(!n1 && !n2)
return NULL;
n1->val+=n2->val;
n1->left = solve(n1->left,n2->left);
n1->right = solve(n1->right,n2->right);
return n1;
}
};
main(){
TreeNode *root1 = new TreeNode(1);
root1->left = new TreeNode(3);
root1->right = new TreeNode(2);
root1->left->left = new TreeNode(5);
TreeNode *root2 = new TreeNode(2);
root2->left = new TreeNode(1);
root2->right = new TreeNode(3);
root2->left->right = new TreeNode(4);
root2->right->right = new TreeNode(7);
Solution ob;
TreeNode *root_res = ob.solve(root1, root2);
inord(root_res);
}輸入
TreeNode *root1 = new TreeNode(1); root1->left = new TreeNode(3); root1->right = new TreeNode(2); root1->left->left = new TreeNode(5); TreeNode *root2 = new TreeNode(2); root2->left = new TreeNode(1); root2->right = new TreeNode(3); root2->left->right = new TreeNode(4); root2->right->right = new TreeNode(7);
輸出
5 4 4 3 5 7
更新於：2020 年 10 月 19 日
146 次瀏覽
廣告