title: 合并二叉树
📃 题目描述
题目链接： 合并二叉树
🔔 解题思路
递归法：采用前序遍历方式进行简单的构造即可，下面是优化的代码；
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (root1 == nullptr) return root2; // 如果root2也是空，那么就返回了nullptr；
if (root2 == nullptr) return root1;
// 以root1这个树作为基本树，改变树的结构；
// 此时root1和root2必然存在 , 采用前序遍历的方式；
root1->val += root2->val;
root1->left = mergeTrees(root1->left, root2->left);
root1->right = mergeTrees(root1->right, root2->right);
return root1;
}
};
迭代法：以root1为答案，更改root1的树结构！依据对称性！采用队列来存储对应的节点，root1和root2中对应的节点val进行相加，但是问题在于：只有一棵树的存在某节点，另一棵树没有，如何解决？ 采用节点转移！可以自己思考，然后看代码：
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (root1 == nullptr) return root2;
if (root2 == nullptr) return root1;
queue que;
que.push(root1);
que.push(root2);
while (!que.empty()) { // 注意：是以root1为基本树结构，改变root1的结构！
TreeNode* cur1 = que.front(); que.pop();
TreeNode* cur2 = que.front(); que.pop();
//cur1 和cur2是一定存在的，非空的, 看后面注释即可知
cur1->val += cur2->val;
// cur1(对应root1树里) 存在左子树，cur2(对应root2树里) 存在左子树
if (cur1->left && cur2->left) {
que.push(cur1->left);
que.push(cur2->left);
}
// cur1(对应root1树里) 存在右子树，cur2(对应root2树里) 存在右子树
if (cur1->right && cur2->right) {
que.push(cur1->right);
que.push(cur2->right);
}
// cur1(对应root1树里) 不存在左子树，cur2(对应root2树里)存在左子树
if (!cur1->left && cur2->left) {
// 将cur2 的左子树转移到cur1中！
cur1->left = cur2->left;
}
// cur1(对应root1树里) 不存在右子树，cur2(对应root2树里)存在右子树
if (!cur1->right && cur2->right) {
// 将cur2 的右子树转移到cur1中！
cur1->right = cur2->right;
}
// 而cur1存在 左/右子树， cur2不存在左/右子树，不需要操作，因为不需要改变cur1 左/右子树的值！
}
return root1;
}
};
💥 复杂度分析
- 时间复杂度：o(n);
- 空间复杂度： O(n);
Original: https://www.cnblogs.com/D-booker/p/16322671.html
Author: D-booker
Title: 15. 合并二叉树
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/713321/
转载文章受原作者版权保护。转载请注明原作者出处！