嘉兴哪家公司做网站比较好的,离婚协议书正规模板,织梦模板免费,html5新增标签力扣日记#xff1a;【二叉树篇】合并二叉树 日期#xff1a;2023.12.18 参考#xff1a;代码随想录、力扣 617. 合并二叉树
题目描述 难度#xff1a;简单 给你两棵二叉树#xff1a; root1 和 root2 。
想象一下#xff0c;当你将其中一棵覆盖到另一棵之上时#xf…力扣日记【二叉树篇】合并二叉树 日期2023.12.18 参考代码随想录、力扣 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
题解
/*** 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 {
#define SOLUTION 2
public:
#if SOLUTION 1 TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if (root1 nullptr root2 nullptr) return nullptr;if (root2 nullptr) {return root1;}if (root1 nullptr) {return root2;}traversal(root1, root2);return root1;}void traversal(TreeNode* root1, TreeNode* root2) {// 把root1当作合并后的树root1-val root1-val root2-val;// 如果root1没有左节点、root2有if (root1-left nullptr root2-left ! nullptr) {// 将root2的左子树作为root1的左子树root1-left root2-left;} // 如果都有左节点(注意这里不能用if要用else if, 因为可能本来没有左节点经过上面的if语句就有了)else if (root1-left ! nullptr root2-left ! nullptr) {// 对左子树进行递归traversal(root1-left, root2-left);}// 如果root1没有右节点、root2有if (root1-right nullptr root2-right ! nullptr) {// 将root2的右子树作为root1的右子树root1-right root2-right;}// 如果都有右节点(注意这里不能用if要用else if, 因为可能本来没有右节点经过上面的if语句就有了)else if (root1-right ! nullptr root2-right ! nullptr) {traversal(root1-right, root2-right);}// 如果是root2-left或root2-right为空则不需要处理}
#elif SOLUTION 2 // 代码随想录ver// 输入参数为两树的根节点返回值为合并后的节点(在tree1上进行修改)TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {// 如果 root1 为空返回 root2if (root1 nullptr) return root2;// 如果 root2 为空返回 root1if (root2 nullptr) return root1;// 如果两者不为空// 中root1-val root2-val;// 递归处理左子树的情况(将tree1左子树与tree2左子树合并并返回合并后的左子树作为root1的左子树)root1-left mergeTrees(root1-left, root2-left);// 递归处理右子树的情况root1-right mergeTrees(root1-right, root2-right);return root1;}
#endif
};复杂度
时间复杂度 空间复杂度
思路总结
我的思路 写的时候好晕绕半天本题还是得从父节点的角度去处理子节点看两个根节点是否有左右节点这里将 root1 作为合并二叉树需要处理①root1没有左节点而root2有左节点 或者 root1、root2都有左节点②root1没有右节点而root2有右节点 或者 root1、root2都有右节点 这些情况对于root1有左(右)节点而root2没有则不需处理注意 if-else if 在本题需要放在恰当的位置先用 if-else if 处理好左节点情况即①、再以相同的方式处理右节点情况即② 代码随想录的思路 看了代码随想录的解法感觉自己的思路真是放屁这才是真正用了合并左右子树的递归啊(我的是单纯递归处理两个根节点去了)同样是在左树的基础上修改这里将合并子树的根节点在每次递归返回对于终止条件 如果 root1 为空此时合并后的树的 root 为 root2返回隐含了对 root2 为空的处理此时返回null)如果 root2 为空此时合并后的树的 root 为 root1返回隐含了对 root1 为空的处理此时返回null 如果都不为空进入递归逻辑前序遍历 中对 左根节点的值进行修改左将 tree1和tree2的左子树合并后的根节点作为左数的左节点右将 tree1和tree2的右子树合并后的根节点作为左数的右节点最终返回合并后的左数根节点root1 迭代 使用队列模拟层序遍历迭代法中一般一起操作两个树都是使用队列模拟类似层序遍历同时处理两个树的节点// TODO
