合并二叉树
# 📃 题目描述
题目链接:617. 合并二叉树 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:
注意: 合并必须从两个树的根节点开始。
# 🔔 解题思路
# 递归
所谓合并也就是两个树的对应节点值相加啦,直接递归遍历两棵树就好了(这里需要遍历两棵树,其实和遍历一棵树没什么区别),哪种遍历方式都可以,这里以前序遍历为例:
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null || root2 == null) {
return root1 == null ? root2 : root1;
}
// 根节点相加
TreeNode root = new TreeNode(root1.val + root2.val);
// 递归合并左子树
root.left = mergeTrees(root1.left, root2.left);
// 递归合并右子树
root.right = mergeTrees(root1.right, root2.right);
return root;
}
}
或者直接在 root1 上面原地相加:
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null || root2 == null) {
return root1 == null ? root2 : root1;
}
// 根节点相加
root1.val += root2.val;
// 递归合并左子树
root1.left = mergeTrees(root1.left, root2.left);
// 递归合并右子树
root1.right = mergeTrees(root1.right, root2.right);
return root1;
}
}
# 迭代
这题用迭代法做也行,也就是层序遍历,将两棵树的节点放入到一个队列中做处理就好了。
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null || root2 == null) {
return root1 == null ? root2 : root1;
}
// 辅助队列
Queue<TreeNode> queue = new LinkedList<>();
// 根节点入队
queue.offer(root1);
queue.offer(root2);
while (!queue.isEmpty()) {
TreeNode node1 = queue.poll();
TreeNode node2 = queue.poll();
// 此时两个节点一定不为空,val 相加
// 直接在 root1 树上操作
node1.val = node1.val + node2.val;
// 如果两棵树左节点都不为空,加入队列
if (node1.left != null && node2.left != null) {
queue.offer(node1.left);
queue.offer(node2.left);
}
// 如果两棵树右节点都不为空,加入队列
if (node1.right != null && node2.right != null) {
queue.offer(node1.right);
queue.offer(node2.right);
}
// 若 node1 的左节点为空,直接赋值
if (node1.left == null && node2.left != null) {
node1.left = node2.left;
}
// 若 node1 的右节点为空,直接赋值
if (node1.right == null && node2.right != null) {
node1.right = node2.right;
}
}
return root1;
}
}
# 💥 复杂度分析
- 空间复杂度:O(LogN)
- 时间复杂度:O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10