[LeetCode] 1305 | All Elements in Two Binary Search Trees

---

문제 링크: https://leetcode.com/problems/all-elements-in-two-binary-search-trees/

---

문제

Given two binary search trees root1 and root2, return a list containing all the integers from both trees sorted in ascending order.

---

조건

• The number of nodes in each tree is in the range [0, 5000].
• $-10^5$ <= Node.val <= $10^5$

---

내 풀이

모든 노드를 돌아다니며 그 value를 모아둔 뒤 정렬해서 출력한다.

시간이 많이 걸릴 줄 알았는데, 꽤 빠른 편에 속한걸 보니 신기했다.

---

코드

# 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 getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
        self.ans = []
        self.dfs(root1)
        self.dfs(root2)
        
        return sorted(self.ans)
        
    def dfs(self, root):
        if not root:    return
        self.ans.append(root.val)
        
        if root.left:
            self.dfs(root.left)
            
        if root.right:
            self.dfs(root.right)