Given two binary search trees root1 and root2, return a list containing all the integers from both trees sorted in ascending order.
Full question details here.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# 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]:
def in_order(root, tree_list):
if root:
in_order(root.left, tree_list)
tree_list.append(root.val)
in_order(root.right, tree_list)
return tree_list
return tree_list
tree_one = in_order(root1, [])
tree_two = in_order(root2, [])
ans = []
idx1 = 0
idx2 = 0
# Merge two lists in order
while idx1 < len(tree_one) and idx2 < len(tree_two):
if tree_one[idx1] < tree_two[idx2]:
ans.append(tree_one[idx1])
idx1 += 1
else:
ans.append(tree_two[idx2])
idx2 += 1
# Exhaust the remaining
while idx1 < len(tree_one):
ans.append(tree_one[idx1])
idx1 += 1
while idx2 < len(tree_two):
ans.append(tree_two[idx2])
idx2 += 1
return ans