[Leetcode] 617. Merge Two Binary Trees

문제 바로가기

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