617.合并二叉树

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

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

返回合并后的二叉树。

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

示例 1：

javascript

   1          2            3
  / \        / \          / \
 3   2  +   1   3   =>   4   5
/           \    \      /   / \
5            4    7    5   4   7

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

示例二
输入：root1 = [1], root2 = [1,2]
输出：[2,2]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-increasing-subsequence

javascript

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {TreeNode}
 */
var mergeTrees = function(root1, root2) {
  if(root1 === null ) return root2
  traversal(root1, root2)
  return root1
}

var traversal = function (root1, root2) {
  if(root1 && root2){
    root1.val = root1.val + root2.val
    if(root1.left && root2.left){
      traversal(root1.left, root2.left)
    }else if(root1.left === null && root2.left){
      root1.left = root2.left
    }
    if(root1.right && root2.right){
      traversal(root1.right, root2.right)
    }else if(root1.right === null && root2.right){
      root1.right = root2.right
    }
  }
}

var mergeTrees = function (root1, root2) {
  if (!root1 && !root2) return null
  if (root1 && !root2) return root1
  if (!root1 && root2) return root2
  root1.val += root2.val
  root1.left = mergeTrees(root1.left, root2.left)
  root1.right = mergeTrees(root1.right, root2.right)
  return root1
}

// test
function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val
  this.left = left === undefined ? null : left
  this.right = right === undefined ? null : right
}

var n1 = new TreeNode(1)
var n2 = new TreeNode(3)
var n3 = new TreeNode(2)
var n4 = new TreeNode(5)
n1.left = n2
n1.right = n3
n2.left = n4
// console.log(n1)

var n5 = new TreeNode(2)
var n6 = new TreeNode(1)
var n7 = new TreeNode(3)
var n8 = new TreeNode(4)
var n9 = new TreeNode(7)
n5.left = n6
n5.right = n7
n6.right = n8
n7.right = n9
// console.log(n5)

console.log(mergeTrees(n1, n5))

617.合并二叉树 #

617.合并二叉树