1932. 合并多棵二叉搜索树 并查集+DFS

1932. 合并多棵二叉搜索树

给你 n 个 二叉搜索树的根节点 ，存储在数组 trees 中（下标从 0 开始），对应 n 棵不同的二叉搜索树。trees 中的每棵二叉搜索树 最多有 3 个节点 ，且不存在值相同的两个根节点。在一步操作中，将会完成下述步骤：

• 选择两个 不同的 下标 i 和 j ，要求满足在 trees[i] 中的某个 叶节点 的值等于 trees[j] 的 根节点的值 。
• 用 trees[j] 替换 trees[i] 中的那个叶节点。
• 从 trees 中移除 trees[j] 。

如果在执行 n - 1 次操作后，能形成一棵有效的二叉搜索树，则返回结果二叉树的 根节点 ；如果无法构造一棵有效的二叉搜索树，返回 null 。

二叉搜索树是一种二叉树，且树中每个节点均满足下述属性：

• 任意节点的左子树中的值都 严格小于 此节点的值。
• 任意节点的右子树中的值都 严格大于 此节点的值。

叶节点是不含子节点的节点。

示例 1：

输入：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]] 。

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

示例 2：

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

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

示例 3：

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

提示：

• n == trees.length
• 1 <= n <= 5 * 1e4
• 每棵树中节点数目在范围 [1, 3] 内。
• 输入数据的每个节点可能有子节点但不存在子节点的子节点
• trees 中不存在两棵树根节点值相同的情况。
• 输入中的所有树都是 有效的二叉树搜索树 。
• 1 <= TreeNode.val <= 5 * 1e4.

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-bsts-to-create-single-bst
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功，这题前后写了两百行，但是写出来了

方法：并查集

1.按根分类，同根的检查，同根有叶子则合并，两个同值的BST根，如果都不是叶子则无解

2. 枚举根节点，找到它的叶子合并

3. 特别地，可能存在一定的循环，比如 [1,2],[2,null,1],这种情况用并查集判别分组，防止重复合并

4.合并完，也不一定是合法的二叉搜索树，比如[1,2]和[2,null,1] 合并后必然存在重复，所以按照BST定义检查一遍

class Solution {
    Map parent = new HashMap<>();
    Map sizes = new HashMap<>();
    public TreeNode canMerge(List trees) {
        //1.改成哈希映射，根->树,同时检查是否有多个同值节点
        Map rootTree = new HashMap<>();
     
        for(TreeNode tree:trees){
            if(!rootTree.containsKey(tree.val)) rootTree.put(tree.val,tree);
            else{
                if(isLeaf(rootTree.get(tree.val))) rootTree.put(tree.val,tree);
                else if(!isLeaf(tree)) return null;
            }
        }
        
        for(Integer key:rootTree.keySet()){
            parent.put(key,key);
            sizes.put(key,1);
        }
 
        Set visited = new HashSet<>();
        //2. 检查树的连通性，能合并的合并
        for(TreeNode t:rootTree.values()){
            if(isLeaf(t)) continue;
            List leafs = new ArrayList<>();
            fillLeafs(t,leafs);
            for(Integer leaf:leafs){
                if(!visited.contains(leaf) && rootTree.containsKey(leaf)){
                      if(isConnect(t.val,leaf)) continue;
                    visited.add(leaf);
                    t = combine(t,rootTree.get(leaf));
                    connect(t.val,leaf);
                }
            }
        }
 
        //移除完所有树，剩下一个有效的
        for(Integer visit:visited) rootTree.remove(visit);
        //没合并完，肯定不行
        if(rootTree.size()!=1) return null;
        TreeNode t = null;
        for(TreeNode tmp:rootTree.values()) t = tmp;
 
        return passCheck(t)?t:null;
    }
    
    private void connect(int a, int b){
        int rootA = getRoot(a);
        int rootB = getRoot(b);
        if(rootA == rootB) return;
        if(sizes.get(rootA)>sizes.get(rootB)){
            parent.put(rootB,rootA);
            sizes.put(rootA,sizes.get(rootA)+sizes.get(rootB));
        }else{
            parent.put(rootA,rootB);
            sizes.put(rootB,sizes.get(rootA)+sizes.get(rootB));
        }
    }
    
    private boolean isConnect(int a,int b){
        return getRoot(a)==getRoot(b);
    }
    
    private int getRoot(int a){
        while(a!=parent.get(a)){
            parent.put(a,parent.get(parent.get(a)));
            a=parent.get(a);
        }
        return a;
    }
    TreeNode pre = null;
    private boolean passCheck(TreeNode root){
        if(root ==null) return true;
        if(!passCheck(root.left)) return false;
        if(pre!=null&&root.val<=pre.val) return false;
        pre = root;
        return passCheck(root.right);
    }
 
    private TreeNode combine(TreeNode p, TreeNode child){
        if(p==null) return null;
        if(isLeaf(p) && p.val==child.val) return child;
        p.left = combine(p.left,child);
        p.right = combine(p.right,child);
        return p;
    }
 
 
 
    void fillLeafs(TreeNode t,List leafs){
        if(t==null) return;
        if(isLeaf(t)){
            leafs.add(t.val);
            return;
        }
        fillLeafs(t.left,leafs);
        fillLeafs(t.right,leafs);
    }
 
    private boolean isLeaf(TreeNode treeNode){
        if(treeNode == null) return false;
        return treeNode.left == null && treeNode.right == null;
    }
}