烟台网站制作工具,做视频网站软件,贵阳网站建设 网站制作,厦门企业网站设计公司题目 难度#xff1a;简单 给你两棵二叉树#xff1a; root1 和 root2 。
想象一下#xff0c;当你将其中一棵覆盖到另一棵之上时#xff0c;两棵树上的一些节点将会重叠#xff08;而另一些不会#xff09;。你需要将这两棵树合并成一棵新二叉树。合并的规则是#xf…题目 难度简单 给你两棵二叉树 root1 和 root2 。
想象一下当你将其中一棵覆盖到另一棵之上时两棵树上的一些节点将会重叠而另一些不会。你需要将这两棵树合并成一棵新二叉树。合并的规则是如果两个节点重叠那么将这两个节点的值相加作为合并后节点的新值否则不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
思路
本题可以通过常见的二叉树的遍历方式同时也是递归的方式同时遍历两棵树每次遍历获取相同的节点然后根据以下三种情况求和 若遍历到的位置均不为空则对两个节点求和将求和的结果覆盖 root2 的这个节点若遍历到的位置root1 为空则返回 root2 的值root2 为空也返回若遍历到的位置root2 为空则返回 root1 的值root1 为空也返回 对代码的图解见代码实现部分
代码实现 本代码采用前序遍历的方式来遍历两棵二叉树 TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {if (root1 nullptr) {return root2;}if (root2 nullptr) {return root1;}root2-val root2-val root1-val;root2-left mergeTrees(root1-left, root2-left);root2-right mergeTrees(root1-right, root2-right);return root2;}下面通过一个示意图来演示递归的效果左树为 root1右树为 root2右侧方框表示函数栈 首先root1 和 root2 入栈此时它们分别指向的值是 1,2按照求和的要求符合情况 1于是 root2 的值更新为 3。
此时代码执行到了 root2-left mergeTrees(root1-left, root2-left); 处我们继续将 root1root2 的左节点传入递归函数。 如图我们看到出现了一个新的函数调用栈此时的 root1 和 root2 为 3 和 1它们分别是传入的上一层函数中的 root1-left 和 root2-left 的值。
同理计算 root2-val root2-val root1-val; 得到 root2 的值为 4。
此时代码执行到了 root2-left mergeTrees(root1-left, root2-left); 处我们继续将 root1root2 的左节点传入递归函数。 在该层递归的代码中因为 root2 为 null所以触发了以下这段代码于是此栈被销毁并返回上一层栈中。 if (root2 nullptr) {return root1;}此时左节点已经处理完了接着处理右节点即红色节点的右节点处理方式同上一步相同。
之后的步骤以此类推就可以完成。
时空复杂度分析
时间复杂度为为 O(n)n 为节点的个数空间复杂度为 O(h)h 为树的高度因为每一层树都要开辟一个新的栈空间
