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/
转载文章受原作者版权保护。转载请注明原作者出处!