LeetCode 题解：617. 合并二叉树，JavaScript，详细注释

2023-08-15
福建
本文字数：739 字
阅读完需：约 2 分钟

原题链接：https://leetcode.cn/problems/merge-two-binary-trees/

这是一道关于二叉树的题目，要求我们合并两棵二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

思路分析：

我们可以使用递归的方法来解决这个问题。具体步骤如下：

基本情况：如果 root1 或 root2 中的任何一个为 null，则返回非空的那个节点。这是因为，如果其中一个节点为 null，那么合并的结果就是另一个节点。
递归情况：如果 root1 和 root2 都不为 null，我们可以创建一个新的节点，其值为 root1.val + root2.val。
递归合并 root1 和 root2 的左子树，并将结果设置为新节点的左子树。
递归合并 root1 和 root2 的右子树，并将结果设置为新节点的右子树。
返回新节点。

代码实现：

function TreeNode(val, left, right) {    this.val = (val===undefined ? 0 : val);    this.left = (left===undefined ? null : left);    this.right = (right===undefined ? null : right);}
var mergeTrees = function(root1, root2) {    // 基本情况    if (root1 === null) return root2;    if (root2 === null) return root1;
    // 创建新节点    let newNode = new TreeNode(root1.val + root2.val);
    // 递归合并左子树和右子树    newNode.left = mergeTrees(root1.left, root2.left);    newNode.right = mergeTrees(root1.right, root2.right);
    return newNode;};

复制代码

这种递归方法的时间复杂度是 O(min(m, n))，其中 m 和 n 分别是两棵树的节点数。因为我们只访问了两棵树中都存在的节点。空间复杂度取决于递归的深度，最坏情况下，递归的深度等于较小的树的高度，所以空间复杂度是 O(min(height1, height2))。

发布于: 刚刚阅读数: 3

Lee Chen

关注

还未添加个人签名 2018-08-29 加入

还未添加个人简介

发布

暂无评论

创作场景

LeetCode 题解：617. 合并二叉树，JavaScript，详细注释

思路分析：

代码实现：

Lee Chen

评论