617. Merge Two Binary Trees

Easy

Problem:

Merge two binary trees. For overlapping nodes, sum the values.

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

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

Solution:

Starting from the root of each binary tree, proceed with the merge, and recursively call the child nodes of each tree to allow the left and right child nodes to also be merged. If a node does not exist on one side, return only the existing node and do not proceed with further recursive calls.

When considering only the return order, the traversal order is Post-Order.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if root1 and root2:
            node = TreeNode(root1.val + root2.val)
            node.left = self.mergeTrees(root1.left, root2.left)
            node.right = self.mergeTrees(root1.right, root2.right)
            return node
        else:
            return root1 or root2