1645. Merge Small Search Trees
An archive keeps a set of tiny index cards, each stored as a binary search tree with one to three nodes. All cards have different root keys, and every key in a card is unique. The input trees lists the cards.
One merge takes two different cards A and B such that some leaf of A (a node with no children, not counting the root of a one-node card) has the same key as the root of B; that leaf is replaced by the whole card B and B is removed from the set. Perform exactly trees.length - 1 merges, choosing them freely.
If this can leave a single tree that is a valid binary search tree (in-order keys strictly increasing), return its root; otherwise return null. When a result exists it is unique. The intended solution is O(n) time with a hash map from root key to card, and it must not use deep recursion.
Example 1
- Input:
- trees = [[8,4],[4,2,6],[6,5,7]]
- Output:
- [8,4,null,2,6,null,null,5,7]
- Explanation:
Hang the tree rooted at 6 on the leaf 6, then the tree rooted at 4 on the leaf 4; the result 8 / 4 / (2, 6 with children 5 and 7) is a valid search tree.
Example 2
- Input:
- trees = [[2,1],[1,null,2]]
- Output:
- []
- Explanation:
Tree 1 has a leaf 2 and tree 2 has a leaf 1, so every root also appears as a leaf and no tree can be the final root; the answer is null.
Example 3
- Input:
- trees = [[5,3,8],[3,1,9]]
- Output:
- []
- Explanation:
Hanging the second tree on leaf 3 puts the key 9 inside the left part of the tree rooted at 5, which breaks the ordering, so the answer is null.
Constraints
1 ≤ trees.length ≤ 200
each tree has 1 to 3 nodes and is a valid binary search tree
1 ≤ node values ≤ 104; no two roots have the same value
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)
- Space
- O(n)