1305. All elements in two binary search trees

leetcode.com/problems/all-elements-in-two-binary-search-trees/

All Elements in Two Binary Search 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 getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
        
        stack1, stack2 = [], []
        output = []
        
        while root1 or root2 or stack1 or stack2 :
            
            while root1 :
                stack1.append(root1)
                root1 = root1.left
                
            while root2 :
                stack2.append(root2)
                root2 = root2.left
                
            if not stack1 or stack2 and stack2[-1].val <= stack1[-1].val :
                root2 = stack2.pop()
                output.append(root2.val)
                root2 = root2.right
            else :
                root1 = stack1.pop()
                output.append(root1.val)
                root1 = root1.right
                
        return output
        

 

정리 :

두 트리 모두 binary search tree 이기 때문에 정렬이 이미 되어있다는 점을 활용.

가능하면 recursive보다 iterative한 방식으로 접근.