All Elements in Two Binary Search Trees - LeetCode
Given two binary search trees root1 and root2, return a list containing all the integers from both trees sorted in ascending order.
Example 1:
Input: root1 = [2,1,4], root2 = [1,0,3] Output: [0,1,1,2,3,4]
Example 2:
Input: root1 = [1,null,8], root2 = [8,1] Output: [1,1,8,8]
Constraints:
The number of nodes in each tree is in the range [0, 5000].
-105 <= Node.val <= 105
- code recursion + sort
class Solution:
def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
def getIntegers(root):
res = []
def helper(root):
if not root: return
helper(root.left)
res.append(root.val)
helper(root.right)
helper(root)
return res
list1 = getIntegers(root1)
list2 = getIntegers(root2)
return sorted(list1 + list2)
- code iterative + merge
class Solution:
def getAllElements(self, root1: TreeNode, root2: TreeNode) -> List[int]:
def getIntegers(root):
res = []
stack = []
while stack or root:
if root:
stack.append(root)
root = root.left
else:
root = stack.pop()
res.append(root.val)
root = root.right
return res
list1 = getIntegers(root1)
list2 = getIntegers(root2)
i = i1 = i2 = 0
res = [0] * (len(list1) + len(list2))
while i < len(res):
if i1 < len(list1) and (i2 == len(list2) or list1[i1] <= list2[i2]):
res[i] = list1[i1]
i1 += 1
else:
res[i] = list2[i2]
i2 += 1
i += 1
return res