617、合并二叉树
1、题目描述
规则：一个二叉树覆盖到另一颗二叉树上。
(1)重复的节点就将节点值做累加 (2)不重复的节点就取并集。
最终得到一个全新的二叉树，如下图所示。
2、分析
分析：也属于构造二叉树，还是采用前序遍历递归遍历即可。
class Solution {
public:
//1.递归函数的入参返回值采用这个就好(入参肯定是两颗二叉树的相同位置节点)
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
//2.函数内首先要明确退出条件(注:这里都换成if……elseif也都是可以的)
//①两个条件都为空就返回空 ②一个空一个不空就返回不空的节点 ③都不空应当作为中间节点处理逻辑
if(!root1 && !root2) return NULL;
if(!root1 && root2) return root2;
if(root1 && !root2) return root1;
//3.接下来就是都不为空了
int new_val = root1->val + root2->val;
TreeNode* root = new TreeNode(new_val);
//4.递归地处理左右子树
root->left = mergeTrees(root1->left, root2->left);
root->right = mergeTrees(root1->right, root2->right);
return root;
}
void levelorder(TreeNode* root){
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
int level_size = que.size();
for(int i = 0; i < level_size; i++){
TreeNode* tmp = que.front();
cout << tmp->val << ",";
que.pop();
if(tmp->left) que.push(tmp->left);
if(tmp->right) que.push(tmp->right);
}
cout << endl;
}
}
};我们可以在上面的基础上继续做一些优化。优化点及优化后的代码如下。
(1)退出条件不用这么复杂，谁为空我就用另一个就好。
(2)其实不用去构造一个全新的二叉树就在root1的基础上改即可。
class Solution {
public:
//1.递归函数的入参返回值采用这个就好(入参肯定是两颗二叉树的相同位置节点)
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
//2.函数内首先要明确退出条件(①root1为空就返回root2 ②root2为空就返回root1)
if(!root1) return root2;
if(!root2) return root1;
//3.接下来就是都不为空(在root1的基础上改就好)
root1->val += root2->val;
//4.递归地处理左右子树
root1->left = mergeTrees(root1->left, root2->left);
root1->right = mergeTrees(root1->right, root2->right);
return root1;
}
};3、实现代码
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <math.h>
using namespace std;
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(): val(0), left(nullptr), right(nullptr){}
TreeNode(int x): val(x), left(nullptr), right(nullptr){}
TreeNode(int x, TreeNode* left, TreeNode* right): val(x), left(left), right(right){}
};
class Solution {
public:
//1.递归函数的入参返回值采用这个就好(入参肯定是两颗二叉树的相同位置节点)
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
//2.函数内首先要明确退出条件(注:这里都换成if……elseif也都是可以的)
//①两个条件都为空就返回空 ②一个空一个不空就返回不空的节点 ③都不空应当作为中间节点处理逻辑
if(!root1 && !root2) return NULL;
if(!root1 && root2) return root2;
if(root1 && !root2) return root1;
//3.接下来就是都不为空了
int new_val = root1->val + root2->val;
TreeNode* root = new TreeNode(new_val);
//4.递归地处理左右子树
root->left = mergeTrees(root1->left, root2->left);
root->right = mergeTrees(root1->right, root2->right);
return root;
}
void levelorder(TreeNode* root){
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
int level_size = que.size();
for(int i = 0; i < level_size; i++){
TreeNode* tmp = que.front();
cout << tmp->val << ",";
que.pop();
if(tmp->left) que.push(tmp->left);
if(tmp->right) que.push(tmp->right);
}
cout << endl;
}
}
};
int main()
{
Solution s1;
TreeNode* t1pnode4 = new TreeNode(5);//new创建指针
TreeNode t1node2(3, t1pnode4, NULL);//创建对象
TreeNode t1node3(2, NULL, NULL);//创建对象
TreeNode root1(1, &t1node2, &t1node3);//创建对象
TreeNode* t2pnode5 = new TreeNode(7);
TreeNode* t2pnode4 = new TreeNode(4);
TreeNode* t2pnode2 = new TreeNode(1);
t2pnode2->right = t2pnode4;
TreeNode t2node3(3,NULL,t2pnode5);
TreeNode root2(2,t2pnode2, &t2node3);
TreeNode* root = s1.mergeTrees(&root1, &root2);
s1.levelorder(root);
}
原文地址：https://blog.csdn.net/mijichui2153/article/details/142724942
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！