【LeetCode刷题日记】617.合并二叉树（空间换安全，还是原地省内存）

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰在这里先祝大家周末愉快然后来到我们每日刷题的环节嗯在此之前我都是想着上午刷题然后顺带着把文章发了但是每次上午都有课然后有时候还起不来所以每次都拖到了下午甚至晚上如果有时间还是每天多刷几题感觉进度有点慢了效率不是很高。摘要本文介绍了合并两棵二叉树的两种方法原地修改法和新建树法。原地修改法直接在root1上进行节点值相加节省空间但会破坏原树结构新建树法则创建全新节点保留原树但消耗更多内存。两种方法均采用深度优先搜索递归实现时间复杂度均为O(min(m,n))。文章通过代码对比和优缺点分析帮助开发者根据实际需求选择合适方案强调了在内存敏感场景下原地修改的优势以及在需要保留原树时的新建树方案。题目背景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]内-104 Node.val 104题目分析整体思路我们拿到这个题目先分析题目需求合并二叉树先从整体上来看就是把两个二叉树进行叠加。之后就是细微的操作相同节点位置的进行节点值的相加依次叠加思维不难具体代码可能看着不是很好实现我们一起来看看吧。代码思路首先我们就要考虑如何找到两棵二叉树的节点位置那么自然就是遍历了这里用什么遍历方法呢其实这里并没有要求因此三种方法都可以。关键是要同时遍历两棵树。合并的方式有两种创建新树每次创建新节点值由两棵树对应节点的值决定都有则相加只有一棵则取该值原地修改复用第一棵树的结构将其值加上第二棵树对应位置的值无论哪种方式当两棵树的对应节点都存在时新节点的值需要两棵树共同提供若只有一棵树有节点则直接继承该节点。具体操作利用递归的方式来实现1.那么首先我们就要先确定递归函数的需要传入的参数和返回值我们既然要同时遍历两颗树那么传入的参数自然就是两棵二叉树的根节点返回值自然就是新的构建的合并二叉树的根节点之后依次递归2.然后确定终止条件因为是传入了两个树那么就有两个树遍历的节点t1 和 t2如果t1 NULL 了两个树合并就应该是 t2 了如果t2也为NULL也无所谓合并之后就是NULL。反过来如果t2 NULL那么两个数合并就是t1如果t1也为NULL也无所谓合并之后就是NULL。3.确定单层递归的逻辑在这里我们需要明确的是我们这里利用的并不是直接构建了一棵新的树而是在第一棵树的基础上进行的叠加。但同时也会破坏原来的树但是节省内存不创建新节点深度优先搜索原地修改思路直接在root1上进行修改将root2的值合并到root1上节省空间。/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { if (root1 null) return root2; if (root2 null) return root1; // 直接在root1上修改 root1.val root2.val; root1.left mergeTrees(root1.left, root2.left); root1.right mergeTrees(root1.right, root2.right); return root1; } }我们也可以自己构建一个新的树深度优先搜索DFS递归思路同时遍历两棵树对应位置相加后创建新节点递归处理左右子树。只需要自己构建一个新的根节点即可。java /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val val; * this.left left; * this.right right; * } * } */ class Solution { public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { // 边界情况其中一棵树为空直接返回另一棵 if (root1 null) return root2; if (root2 null) return root1; // 两棵树都不为空创建新节点值为两节点值之和 TreeNode merged new TreeNode(root1.val root2.val); // 递归合并左右子树 merged.left mergeTrees(root1.left, root2.left); merged.right mergeTrees(root1.right, root2.right); return merged; } }代码对比对比项方法一创建新树方法二原地修改核心代码TreeNode merged new TreeNode(root1.val root2.val)root1.val root2.val是否创建新节点✅ 是每层递归都 new❌ 否直接在原节点上修改是否修改原树❌ 否root1和root2保持不变✅ 是root1被改变返回结果返回新创建树的根节点返回修改后的root1优缺点对比维度方法一创建新树方法二原地修改空间复杂度O(min(m,n)) 新树空间O(min(m,n))额外内存需要创建新节点约 mn 个节点几乎无额外内存是否破坏原数据❌ 不破坏✅ 破坏 root1函数纯度✅ 纯函数无副作用❌ 有副作用可重入性✅ 可重复调用❌ 原数据被改后无法恢复结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励