# [Leetcode] 617. Merge Two Binary Trees

haebin·2021년 6월 24일
0

## 코딩테스트

목록 보기
62/65

문제 바로가기

root부터 탐색하면서 left child, right child에 아래 단계 적용

1. 같은 위치에 node가 있으면 값 합치기
2. 하나만 존재하면 해당 node 주소를 child에 저장

Time Complexity: $O(n)$
Space Complexity: $O(n)$ - worst case(skewed tree) / $O(\log{n})$ - average

Runtime: 76 ms, faster than 97.44% of Python3 online submissions for Merge Two Binary Trees.
Memory Usage: 15.4 MB, less than 73.80% of Python3 online submissions for Merge Two Binary Trees.

# 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: TreeNode, root2: TreeNode) -> TreeNode:
if root1:
if root2:
root1.val += root2.val
else:
return root1
else:
return root2

def dfs(root1: TreeNode, root2: TreeNode):
if root1.left:
if root2.left:
root1.left.val += root2.left.val
dfs(root1.left, root2.left)
else:
root1.left = root2.left

if root1.right:
if root2.right:
root1.right.val += root2.right.val
dfs(root1.right, root2.right)
else:
root1.right = root2.right

dfs(root1, root2)
return root1

### solution

left, right child를 하나하나 계산하지 않고 다음 recursion에서 해결하게 함으로써 더 간단하게 줄일 수 있었다.

Time Complexity: $O(n)$
Space Complexity: $O(n)$ - worst case(skewed tree) / $O(\log{n})$ - average

Runtime: 84 ms, faster than 77.93% of Python3 online submissions for Merge Two Binary Trees.
Memory Usage: 15.5 MB, less than 48.12% of Python3 online submissions for Merge Two Binary Trees.

# 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: TreeNode, root2: TreeNode) -> TreeNode:
if root1 is None:
return root2
if root2 is None:
return root1

root1.val += root2.val
root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)

return root1