江门网站优化公司,金坛住房和城乡建设局网站,深圳今天新闻头条,哈尔滨网站公司前言
二叉树篇#xff0c;继续。 记录 五十二【617.合并二叉树】 一、题目阅读
给你两棵二叉树#xff1a; root1 和 root2 。
想象一下#xff0c;当你将其中一棵覆盖到另一棵之上时#xff0c;两棵树上的一些节点将会重叠#xff08;而另一些不会#xff09;。你需要…前言
二叉树篇继续。 记录 五十二【617.合并二叉树】 一、题目阅读
给你两棵二叉树 root1 和 root2 。
想象一下当你将其中一棵覆盖到另一棵之上时两棵树上的一些节点将会重叠而另一些不会。你需要将这两棵树合并成一棵新二叉树。合并的规则是如果两个节点重叠那么将这两个节点的值相加作为合并后节点的新值否则不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
示例 1
输入root1 [1,3,2,5], root2 [2,1,3,null,4,null,7]
输出[3,4,5,5,4,null,7]示例 2
输入root1 [1], root2 [1,2]
输出[2,2]提示
两棵树中的节点数目在范围 [0, 2000] 内
-10^4 Node.val 10^4二、尝试实现
思路
本题需要同时操作两个树那么学过记录 四十二【101. 对称二叉树】 的方法是同时操作两个树。所以同样的思路解决这道题。通过递归实现开始分步完成递归函数。确定递归的参数因为同时操作两个树所以两个参数TreeNode* root1和TreeNode* root2。确定递归返回值返回合并之后的子树。所以返回值类型TreeNode* 。确定终止条件
root1和root2都是空返回空节点root1或root2只有一个为空返回不为空的节点root1和root2都不是空进入递归处理逻辑。
递归逻辑本题也相当于构造一个新的二叉树——记录 五十一【654.最大二叉树】中学习到使用前序遍历。
先创建中间节点。值为root1-valroot2-val。递归左子树递归右子树。
代码实现
/*** Definition for a binary tree node.* 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:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {//终止条件if(!root1 !root2) return nullptr;if(!root1 root2) return root2;if(root1 !root2) return root1;//两个同时存在时处理顺序前序中左右TreeNode* root new TreeNode(root1-valroot2-val);root-left mergeTrees(root1-left,root2-left);root-right mergeTrees(root1-right,root2-right);return root;}
};三、参考学习
参考学习链接
学习内容
递归法思路和二、中的思路一致但是代码处理上的区别如下
终止条件 参考给的终止条件同时为空的逻辑在这两行中可以涵盖。if (t1 NULL) return t2; // 如果t1为空合并之后就应该是t2
if (t2 NULL) return t1; // 如果t2为空合并之后就应该是t1二、中代码实现的终止条件分成3类。 新定义树或重复利用某一个树 参考在合并时重复利用root1这个树在这个树上合并操作。没有新定义在二、中代码实现中新定义树节点自然可以重复利用root2这个树root2-val root1-val; 遍历顺序根据学习经验方便理解可以确定前序遍历好理解。但是重复利用某个树的时候前中后遍历顺序都可以。 迭代法同样需要同时处理两个树。那么处理的两个对象需要同时放到容器中类似记录 四十二【101. 对称二叉树】中迭代实现。 迭代代码实现 /*** Definition for a binary tree node.* 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:TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {queueTreeNode* q;if(!root1) return root2;if(!root2) return root1;q.push(root1);q.push(root2);while(!q.empty()){TreeNode* node1 q.front();q.pop();TreeNode* node2 q.front();q.pop();//复用root1node1-val node2-val;if(node1-left node2-left){q.push(node1-left);q.push(node2-left);}if(node1-right node2-right){q.push(node1-right);q.push(node2-right);}//复用树1所以用树1的左右判断是否为空。if(!node1-left){node1-left node2-left;}if(!node1-right){node1-right node2-right;}}return root1;}
};总结
【617.合并二叉树】用到的知识点学习过能够想到并应用即可。 学习记录
同时操作两个树记录 四十二【101. 对称二叉树、100.相同的树、572.另一个树的子树】构造二叉树记录 五十一【654.最大二叉树】
欢迎指正转载标明出处
