Readme

1932.Merge-BSTs-to-Create-Single-BST

本题的突破口在于root的选择。因为我们要合并所有的小BST，所以说明任何小BST的任何子节点肯定不会是合并得到的大BST的根节点（如果是的话，那么这棵大BST就会有重复的元素）。所以大BST的根节点肯定不会出现在所有小BST的子节点里。于是，我们将所有小BST的子节点放入一个集合nodeVals里面，再逐一查看哪个小BST的根节点没有出现在nodeVals里。注意，这样的根节点只会有一个。假设有两个小BST的根节点A和B都不在nodeVals里，那么如果以A为大BST的根节点进行合并时，因为没有任何小BST的子节点等于B，那么根据规则，B永远都不会被merge进来。

根据以上分析，我们就可以通过nodeVals，确定哪个小BST是作为合并大BST的根root。然后我们就以其为根进行构造整棵树。

接下来的一个问题，我们从root下沉到了叶子节点C，然后发现C恰好是某个小BST的根，那么我们是否一定要把那个小BST就在此处merge进来呢？结论是需要，因为最终整颗大BST的所有节点元素都是unique的，一棵符合要求的大BST不会在其他地方再出现C了。此时我们不去合并，那么那个以C为根的小BST就永远没机会被合并进来。所以我们在从root往下沉的过程中，一定遇到某个叶子节点与某棵小BST的根相同，那么就把那个小BST拼接过来，然后继续递归下沉。

接下来的一个问题，如果我们拼接了一个小BST，那么这样的拼接是否满足整颗大BST的性质呢？这就需要检验。检验的方法和简单，就是在dfs下沉的过程中带上对于子树的range限制。比如对于整颗大BST的根，我们的range是[INT_MIN,INT_MAX]：那么对于根的左孩子，它的range应该是[INT_MIN, root->val-1]；对于根的右孩子，它的range应该是[root->val+1，INT_MAX]。以此类推，我们一边拼接小BST，一边下沉检查每个节点的val和range，一旦发现节点的val不符合range要求，那么就说明这违反了BST的性质，就可以返回false表示构建这样的大BST一定是失败的。

另外还有一点需要检查的：是否所有的小BST都被merge进来。所以我们用一个集合来收录所有构造过程中被merge的小BST的根，最终检查集合的大小是否为n。