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

[chencl1986]

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

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

思路分析：

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

1. 基本情况：如果 root1 或 root2 中的任何一个为 null，则返回非空的那个节点。这是因为，如果其中一个节点为 null，那么合并的结果就是另一个节点。

2. 递归情况：如果 root1 和 root2 都不为 null，我们可以创建一个新的节点，其值为 root1.val + root2.val。

3. 递归合并 root1 和 root2 的左子树，并将结果设置为新节点的左子树。

4. 递归合并 root1 和 root2 的右子树，并将结果设置为新节点的右子树。

5. 返回新节点。

代码实现：

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))。