[LeetCode] Medium - 1305. All Elements in Two Binary Search Trees (?)

Source From Here

Question
Given two binary search trees root1 and root2.

Return a list containing all the integers from both trees sorted in ascending order:


Constraints:

* Each tree has at most 5000 nodes.
* Each node's value is between [-10^5, 10^5].

Solution

Naive

view plaincopy to clipboardprint?

1. # Definition for a binary tree node.  
2. # class TreeNode:  
3. #     def __init__(self, x):  
4. #         self.val = x  
5. #         self.left = None  
6. #         self.right = None  
7.   
8. class Solution:  
9.     def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:          
10.         # 1) Collecting values of two trees  
11.         list1 = []  
12.         list2 = []  
13.         def inorder(node, alist):  
14.             if node is None:  
15.                 return   
16.               
17.             if node.left:  
18.                 inorder(node.left, alist)  
19.                   
20.             alist.append(node.val)  
21.               
22.             if node.right:  
23.                 inorder(node.right, alist)  
24.           
25.         inorder(root1, list1)  
26.         inorder(root2, list2)  
27.           
28.         # 2) Conducting mergesort  
29.         rlist = []  
30.         while list1 and list2:  
31.             if list1[0] < list2[0]:  
32.                 rlist.append(list1.pop(0))  
33.             else:  
34.                 rlist.append(list2.pop(0))  
35.           
36.         if list1:  
37.             rlist.extend(list1)  
38.           
39.         if list2:  
40.             rlist.extend(list2)  
41.               
42.         return rlist  

Runtime: 392 ms, faster than 45.72% of Python3 online submissions for All Elements in Two Binary Search Trees.
Memory Usage: 21.6 MB, less than 100.00% of Python3 online submissions for All Elements in Two Binary Search Trees.

Discussion (link)

view plaincopy to clipboardprint?

1. class Solution:  
2.     def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:          
3.         def gen(node):  
4.             if node:  
5.                 yield from gen(node.left)  
6.                 yield node.val  
7.                 yield from gen(node.right)  
8.                   
9.         return list(heapq.merge(gen(root1), gen(root2)))  

Runtime: 3556 ms, faster than 5.01% of Python3 online submissions for All Elements in Two Binary Search Trees.
Memory Usage: 23.5 MB, less than 100.00% of Python3 online submissions for All Elements in Two Binary Search Trees.

Supplement
* FAQ - In practice, what are the main uses for the new "yield from" syntax in Python 3.3?