525. Two Trees, One Order
Two neighbouring orchards each keep their trees' crop yields in a binary search tree: yields in the left part of a tree are strictly smaller than the tree's yield and those in the right part strictly larger. The orchards are merging their reports.
Given the roots a and b of the two search trees, return an array containing every key of both trees in non-decreasing order. A key that appears in both trees must appear twice in the answer. Either tree may be empty; if both are empty return an empty array.
Example 1
- Input:
- a = [10,4,18], b = [7,2,12]
- Output:
- [2,4,7,10,12,18]
- Explanation:
The in-order keys of the trees are 4, 10, 18 and 2, 7, 12; merged they give 2, 4, 7, 10, 12, 18.
Example 2
- Input:
- a = [6,null,9], b = []
- Output:
- [6,9]
- Explanation:
The second tree is empty, so the answer is just the keys of the first tree in order.
Constraints
0 ≤ number of nodes in each tree ≤ 5000
-105 ≤ node value ≤ 105
Each tree is a valid binary search tree with distinct keys inside the tree; the two trees may share keys
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(h1 + h2)