合并多棵二叉搜索树

输入：trees = [[2,1],[3,2,5],[5,4]]
输出：[3,2,5,1,null,4]
解释：
第一步操作中，选出 i=1 和 j=0 ，并将 trees[0] 合并到 trees[1] 中。
删除 trees[0] ，trees = [[3,2,5,1],[5,4]] 。

在第二步操作中，选出 i=0 和 j=1 ，将 trees[1] 合并到 trees[0] 中。
删除 trees[1] ，trees = [[3,2,5,1,null,4]] 。

结果树如上图所示，为一棵有效的二叉搜索树，所以返回该树的根节点。

输入：trees = [[5,3,8],[3,2,6]]
输出：[]
解释：
选出 i=0 和 j=1 ，然后将 trees[1] 合并到 trees[0] 中。
删除 trees[1] ，trees = [[5,3,8,2,6]] 。

结果树如上图所示。仅能执行一次有效的操作，但结果树不是一棵有效的二叉搜索树，所以返回 null 。

输入：trees = [[5,4],[3]]
输出：[]
解释：无法执行任何操作。

class Solution {
public:
    TreeNode* canMerge(vector<TreeNode*>& trees) {
        // 存储所有叶节点值的哈希集合
        unordered_set<int> leaves;
        // 存储 (根节点值, 树) 键值对的哈希映射
        unordered_map<int, TreeNode*> candidates;
        for (TreeNode* tree: trees) {
            if (tree->left) {
                leaves.insert(tree->left->val);
            }
            if (tree->right) {
                leaves.insert(tree->right->val);
            }
            candidates[tree->val] = tree;
        }
 
        // 存储中序遍历上一个遍历到的值，便于检查严格单调性
        int prev = 0;
        
        // 中序遍历，返回值表示是否有严格单调性
        function<bool(TreeNode*)> dfs = [&](TreeNode* tree) {
            if (!tree) {
                return true;
            }
 
            // 如果遍历到叶节点，并且存在可以合并的树，那么就进行合并
            if (!tree->left && !tree->right && candidates.count(tree->val)) {
                TreeNode* candidate = candidates[tree->val];
                // 检查合并前的树是否符合二叉搜索树的条件
                if (!isBST(candidate)) {
                    return false;
                }
                tree->left = candidate->left;
                tree->right = candidate->right;
                // 合并完成后，将树从哈希映射中移除，以便于在遍历结束后判断是否所有树都被遍历过
                candidates.erase(tree->val);
            }
            
            // 先遍历左子树
            if (!dfs(tree->left)) {
                return false;
            }
            // 再遍历当前节点
            if (tree->val <= prev) {
                return false;
            };
            prev = tree->val;
            // 最后遍历右子树
            return dfs(tree->right);
        };
        
        for (TreeNode* tree: trees) {
            // 寻找合并完成后的树的根节点
            if (!leaves.count(tree->val)) {
                // 将其从哈希映射中移除
                candidates.erase(tree->val);
                // 从根节点开始进行遍历
                // 如果中序遍历有严格单调性，并且所有树的根节点都被遍历到，说明可以构造二叉搜索树
                return (dfs(tree) && candidates.empty()) ? tree : nullptr;
            }
        }
        return nullptr;
    }
    
    // 判断一棵树是否是二叉搜索树
    bool isBST(TreeNode* root) {
        stack<TreeNode*> stk;
        TreeNode* pre = nullptr;
        while (root || !stk.empty()) {
            while (root) {
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            if (pre && root->val <= pre->val) {
                return false;
            }
            pre = root;
            root = root->right;
        }
        return true;
    }
};