[3]] Output: [] Explanation: It is impossible to perform any operations.

Constraints

n == trees.length
1 <= n <= 5 * 10^4
The number of nodes in each tree is in the range [1, 3].
Each node in the input may have children but no grandchildren.
No two roots of trees have the same value.
All the trees in the input are valid BSTs.
1 <= TreeNode.val <= 5 * 10^4.

Solution

Method 1 – Hash Mapping and DFS Merge

Intuition

Since each BST has at most 3 nodes and no two roots have the same value, we can use a hash map to quickly find which tree can be merged at a leaf. By recursively merging trees at leaves, we can attempt to build a single BST. After merging, we must check if the result is a valid BST and contains all nodes.

Approach

Build a map from root value to tree for quick lookup.
For each tree, count leaf values and root values to find the unique root (the one not referenced as a leaf).
Starting from the unique root, recursively merge trees at leaves using DFS.
After merging, check if the resulting tree is a valid BST and contains all nodes.
If valid, return the root; otherwise, return null.

Code

[{"language":"C++","code":"struct TreeNode {\n    int val;\n    TreeNode *left, *right;\n    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n};\nclass Solution {\npublic:\n    TreeNode* canMerge(vector<TreeNode*>& trees) {\n        unordered_map<int, TreeNode*> mp;\n        unordered_map<int, int> leafCount;\n        for (auto t : trees) {\n            mp[t->val] = t;\

Related Tags