617.重组二叉树（javascript）617.MergeTwoBinaryTrees

这里有两个二叉树： root1 和 root2 。

想象一下，当您将其中一个覆盖在另一个上时，两棵树上的一些节点会重叠（而其他节点不会重叠）。您需要将这两棵树合并为一棵新的二叉树。合并的规则是：如果两个节点重叠，则将两个节点的值相加，作为合并节点的新值； null 该节点将直接用作新二叉树的节点。

返回合并的二叉树。

注意: 合并过程必须从两个树的根节点开始。

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

示例 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

解题思路

您可以使用深度优先搜索合并两个二叉树。从根节点开始，同时遍历两个二叉树并合并相应的节点。

• 两个二叉树的对应节点可能有以下三种情况，每种情况使用不同的合并方法。
• 如果两个二叉树的对应节点为空，则合并后的二叉树对应节点也为空；
• 如果两个二叉树的对应节点中只有一个是空的，则合并后的二叉树对应节点为非空节点；
• 如果两个二叉树的对应节点不为空，则合并的二叉树对应节点的值是两个二元树对应节点值的总和。此时，需要显式合并这两个节点。

先序遍历

var mergeTrees = function(root1, root2) {
    if(root1==null) return root2
    if(root2==null) return root1

    root1.val+=root2.val
    root1.left=mergeTrees(root1.left,root2.left)
    root1.right=mergeTrees(root1.right,root2.right)

    return root1
};

中序遍历

var mergeTrees = function(root1, root2) {
    if(root1==null) return root2
    if(root2==null) return root1

    root1.left=mergeTrees(root1.left,root2.left)
    root1.val+=root2.val
    root1.right=mergeTrees(root1.right,root2.right)

    return root1
};

后序遍历

var mergeTrees = function(root1, root2) {
    if(root1==null) return root2
    if(root2==null) return root1

    root1.left=mergeTrees(root1.left,root2.left)
    root1.right=mergeTrees(root1.right,root2.right)
    root1.val+=root2.val

    return root1
};

leetcode： https://leetcode-cn.com/problems/merge-two-binary-trees/