数据结构
网络
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 次浏览
广告