617. Merge Two Binary Trees

Problem

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.

Example 1:

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

Example 2:

Input: root1 = [1], root2 = [1,2]
Output: [2,2]

Constraints:

• The number of nodes in both trees is in the range [0, 2000].
• 104 <= Node.val <= 104

Problem Summary

Given two binary trees, imagine that when you cover one of them with the other, some nodes of the two binary trees will overlap. You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, their values are added together as the new value of the merged node; otherwise, the node that is not NULL will be used directly as the node of the new binary tree.

Solution Approach

• Easy problem. Use a depth-first search approach: start from the root nodes and traverse the two binary trees simultaneously, merging the corresponding nodes. The corresponding nodes of the two binary trees may fall into the following three cases:
  • If the corresponding nodes of both binary trees are empty, then the corresponding node of the merged binary tree is also empty;
  • If only one of the corresponding nodes of the two binary trees is empty, then the corresponding node of the merged binary tree is the non-empty node;
  • If the corresponding nodes of both binary trees are not empty, then the value of the corresponding node of the merged binary tree is the sum of the values of the corresponding nodes of the two binary trees; in this case, the two nodes need to be explicitly merged.
• After merging a node, its left and right subtrees also need to be merged separately. This can be implemented with recursion.

Code

package leetcode

import (
	"github.com/halfrost/leetcode-go/structures"
)

// TreeNode define
type TreeNode = structures.TreeNode

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
	if root1 == nil {
		return root2
	}
	if root2 == nil {
		return root1
	}
	root1.Val += root2.Val
	root1.Left = mergeTrees(root1.Left, root2.Left)
	root1.Right = mergeTrees(root1.Right, root2.Right)
	return root1
}