[LeetCode] Merge BSTs to Create Single BST

1932. Merge BSTs to Create Single BST

You are given n BST (binary search tree) root nodes for n separate BSTs stored in an array trees (0-indexed). Each BST in trees has at most 3 nodes, and no two roots have the same value. In one operation, you can:

  • Select two distinct indices i and j such that the value stored at one of the leaves of trees[i] is equal to the root value of trees[j].
  • Replace the leaf node in trees[i] with trees[j].
  • Remove trees[j] from trees.

Return the root of the resulting BST if it is possible to form a valid BST after performing n - 1 operations, or null if it is impossible to create a valid BST.

A BST (binary search tree) is a binary tree where each node satisfies the following property:

  • Every node in the node’s left subtree has a value strictly less than the node’s value.
  • Every node in the node’s right subtree has a value strictly greater than the node’s value.

A leaf is a node that has no children.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
int cnt = 0;
bool valid(TreeNode* node, int mi, int ma) {
if(!node) return true;
cnt--;
if(mi >= node->val or ma <= node->val) return false;
if(!valid(node->left, mi, node->val)) return false;
if(!valid(node->right, node->val, ma)) return false;
return true;
}
public:
TreeNode* canMerge(vector<TreeNode*>& trees) {
unordered_map<int, TreeNode*> roots, children;
for(auto tree : trees) {
roots[tree->val] = tree;
cnt++;
if(tree->left) {
children[tree->left->val] = tree->left;
cnt++;
}
if(tree->right) {
children[tree->right->val] = tree->right;
cnt++;
}
}

for(auto& p : children) {
if(roots.count(p.first)) {
p.second->left = roots[p.first]->left;
p.second->right = roots[p.first]->right;
roots.erase(p.first);
cnt--;
}
}
if(roots.size() != 1 or !valid(roots.begin()->second, INT_MIN, INT_MAX)) return nullptr;
return cnt == 0 ? roots.begin()->second : nullptr;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/03/17/PS/LeetCode/merge-bsts-to-create-single-bst/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.