Merge Two Binary Trees

1. Problem Description

Given two binary trees, imagine overlaying one tree on top of the other so that some nodes overlap.

Merge them into a new binary tree. If two nodes overlap, add their values as the new node value; otherwise use the non-null node directly in the merged tree.

2. Approach

1. Approach 1
   • Preorder traversal: add root.Val, then set left to the merge of the left subtrees and right to the merge of the right subtrees

3. Implementation

/**
 * 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 = root1.Val + root2.Val
    root1.Left = mergeTrees(root1.Left, root2.Left)
    root1.Right = mergeTrees(root1.Right, root2.Right)
    return root1
}

4. References

• 617. Merge Two Binary Trees - LeetCode