13.合并二叉树（617）

一、题目内容 简单

给你两棵二叉树： root1 和 root2 。

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

返回合并后的二叉树。

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

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

二、解题思路

二叉树使用递归，就要想使用前中后哪种遍历方式？
本题使用哪种遍历都是可以的！
我们下面以前序遍历为例。
动画如下：

那么我们来按照递归三部曲来解决：

1. 确定递归函数的参数和返回值：

首先那么要合入两个二叉树，那么参数至少是要传入两个二叉树的根节点，返回值就是合并之后二叉树的根节点。
代码如下：

var mergeTrees = function (root1, root2) {}

1. 确定终止条件：

因为是传入了两个树，那么就有两个树遍历的节点 root1 和 root2，如果root1 === null了，两个树合并就应该是 root2 了啊（如果 root2 也为 null 也无所谓，合并之后就是 null）。
反过来如果root2 === null，那么两个数合并就是 root1（如果 root1 也为 null 也无所谓，合并之后就是 null）。
代码如下：

if (!root1) return root2
if (!root2) return root1

1. 确定单层递归的逻辑：

单层递归的逻辑就比较好些了，这里我们用重复利用一下t1这个树，t1就是合并之后树的根节点（就是修改了原来树的结构）
那么单层递归中，就要把两棵树的元素加到一起

const root = new TreeNode(root1.val + root2.val)
root.left = mergeTrees(root1.left, root2.left)
root.right = mergeTrees(root1.right, root2.right)
return root

三、具体代码

/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {TreeNode}
 */
var mergeTrees = function (root1, root2) {
  if (!root1) return root2
  if (!root2) return root1
  const root = new TreeNode(root1.val + root2.val)
  root.left = mergeTrees(root1.left, root2.left)
  root.right = mergeTrees(root1.right, root2.right)
  return root
};

四、其他解法

迭代法

求二叉树对称的时候就是把两个树的节点同时加入队列进行比较。
本题我们也使用队列，模拟的层序遍历，代码如下：

/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {TreeNode}
 */
var mergeTrees = function (root1, root2) {
  if (!root1) return root2
  if (!root2) return root1
  const queue = [root1, root2]
  while (queue.length) {
    const node1 = queue.shift()
    const node2 = queue.shift()
    node1.val += node2.val
    if (node1.left && node2.left) {
      queue.push(node1.left, node2.left)
    }
    if (node1.right && node2.right) {
      queue.push(node1.right, node2.right)
    }
    if (!node1.left && node2.left) {
      node1.left = node2.left
    }
    if (!node1.right && node2.right) {
      node1.right = node2.right
    }
  }
  return root1
};