두 이진 트리 병합

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

Merge Two Binary Trees - LeetCode

 

 

 이 문제는 재귀탐색으로 해결할 수 있다.

# 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, t1: Optional[TreeNode], t2: Optional[TreeNode]) -> Optional[TreeNode]:
        if t1 and t2:
            node=TreeNode(t1.val + t2.val)
            node.left=self.mergeTrees(t1.left,t2.left)
            node.right=self.mergeTrees(t1.right,t2.right)
            
            return node
        elif t1:
            return t1
        elif t2:
            return t2
            
        else:
            return

 각각 이진 트리의 루트부터 시작해 합쳐 나가면서 좌, 우 자식 노드 또한 병합될 수 있도록 각 트리 자식 노드를 재귀 호출한다. 만약 어느 한쪽에 노드가 존재하지 않는다면 존재하는 노드만 리턴하고 더 이상 재귀 호출을 진행하지 않는다.