617. Merge Two Binary Trees

将两个二叉树合并为一个新的二叉树。合并的规则是，如果两个节点重叠，将值相加作为节点合并后的新值，否则不为null的节点将直接作为新二叉树的节点。

DFS

• 时间复杂度：O(min(m,n))，其中m 和 n 分别是两个二叉树节点的个数。对两个二叉树同时进行深度优先遍历，只有当两个二叉树中的对应节点都不为空时才会对该节点进行显性合并操作，因此被访问到的节点树不会超过较小的二叉树的节点数。
• 空间复杂度：O(min(m,n))，空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的节点数，最坏情况下，二叉树的高度等于节点数。
• Runtime: 120 ms, faster than 48.79%
• Memory Usage: 46.2 MB, less than 73.66%

var mergeTrees = function(root1, root2) {
    if(root1 === null) return root2
    if(root2 === null) return root1
    let merged = new TreeNode(root1.val + root2.val)
    merged.left = mergeTrees(root1.left, root2.left)
    merged.right = mergeTrees(root1.right, root2.right)
    return merged
};

BFS

广度优先遍历，将值附加到root1上。

• Runtime: 112 ms, faster than 81.63%
• Memory Usage: 46.3 MB, less than 54.52%

var mergeTrees = function(root1, root2) {
    if(root1 === null || root2 === null) return root1 || root2
    let queue = [[root1, root2]]
    while(queue.length) {
        let [n1, n2] = queue.shift()
        let { left: l1, right: r1 } = n1
        let { left: l2, right: r2 } = n2
        
        if(n1 && n2) n1.val += n2.val
        if(l1 && l2) queue.push([l1, l2])
        if(r1 && r2) queue.push([r1, r2])
        
        if(!l1 && l2) n1.left = n2.left
        if(!r1 && r2) n1.right = n2.right
    }
    return root1
};