物流网站的建设,wordpress电视直播插件下载,品牌网站建设内容,一键优化大师给定两个二叉树#xff0c;想象当你将它们中的一个覆盖到另一个上时#xff0c;两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠#xff0c;那么将他们的值相加作为节点合并后的新值#xff0c;否则不为 NULL 的节点将直接… 给定两个二叉树想象当你将它们中的一个覆盖到另一个上时两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠那么将他们的值相加作为节点合并后的新值否则不为 NULL 的节点将直接作为新二叉树的节点。 思路 如何同时遍历两棵树呢
和遍历一棵树逻辑一致但是传入的参数为两个树的节点同时操作。
递归
前中后序遍历都可以以前序遍历为例
1. 确定递归的参数和返回值
传入的参数为两颗二叉树的根节点返回值是合并后的二叉树的根节点。
2. 确定终止条件
传入两棵树后那么就有两个树遍历的节点t1和t2如果 t1NULL则两棵树合并为 t2。
if (t1 NULL) return t2; // 如果t1为空合并之后就应该是t2
if (t2 NULL) return t1; // 如果t2为空合并之后就应该是t1
3. 单层递归的逻辑
重复利用树 t1t1就是合并后的树的根节点。
单层递归中将两棵树的元素相加。
t1-left mergeTrees(t1-left, t2-left);
t1-right mergeTrees(t1-right, t2-right);
return t1;
合并代码
class Solution {
public:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if(root1 NULL) return root2;if(root2 NULL) return root1;root1-left mergeTrees(root1-left, root2-left);root1-right mergeTrees(root1-right, root2-right);root1-val root2-val;return root1;}
};
重新定义一棵树作为合并后的新树
class Solution {
public:TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {if (t1 NULL) return t2;if (t2 NULL) return t1;// 重新定义新的节点不修改原有两个树的结构TreeNode* root new TreeNode(0);root-val t1-val t2-val;root-left mergeTrees(t1-left, t2-left);root-right mergeTrees(t1-right, t2-right);return root;}
};
