#1932
Merge BSTs to Create Single BST
master · 1760 · lc hard +32 · failed · 38.1% accepted · 657 likes · top 17%
Description
You are given an array trees of n BST root nodes (each tree has at most 3 nodes, root values all distinct). In one operation:
- Pick i and j (i != j) where a leaf value of trees[i] equals the root value of trees[j].
- Replace that leaf with the entire trees[j], then remove trees[j] from trees.
After n - 1 operations, return the resulting BST root if valid, or null if impossible.
Example 1:
Input: trees = [[2,1],[3,2,5],[5,4]]
Output: [3,2,5,1,null,4]
Explanation:
In the first operation, pick i=1 and j=0, and merge trees[0] into trees[1].
Delete trees[0], so trees = [[3,2,5,1],[5,4]].
Example 2:
In the second operation, pick i=0 and j=1, and merge trees[1] into trees[0].
Delete trees[1], so trees = [[3,2,5,1,null,4]].
Example 3:
The resulting tree, shown above, is a valid BST, so return its root.
Example 4:
Input: trees = [[5,3,8],[3,2,6]]
Output: []
Explanation:
Pick i=0 and j=1 and merge trees[1] into trees[0].
Delete trees[1], so trees = [[5,3,8,2,6]].
Example 5:
The resulting tree is shown above. This is the only valid operation that can be performed, but the resulting tree is not a valid BST, so return null.
Example 6:
Input: trees = [[5,4],[3]]
Output: []
Explanation: It is impossible to perform any operations.
Code
1
2
3
4
5
6
7
8
9