1932. 合并多个二叉搜索树

Hard

题目描述

给你 n 个二叉搜索树的根节点，存储在数组 trees 中（下标从 0 开始），对应 n 棵独立的二叉搜索树。每棵二叉搜索树 trees[i] 中的节点数最多为 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]

示例 2：

输入：trees = [[5,3,8],[3,2,6]]
输出：[]

示例 3：

输入：trees = [[5,4],[3]]
输出：[]

提示：

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

解题思路

这道题需要将多个小的二叉搜索树合并成一个大的二叉搜索树。关键思路是：

核心观察：

最终的根节点一定是某个树的根节点，且这个根节点的值不能出现在其他树的叶节点中
如果一个根节点值出现在某个叶节点中，说明这棵树会被合并到其他树中

算法步骤：

找到最终根节点：遍历所有树，统计每个根节点值在所有叶节点中的出现次数。只有出现次数为0的根节点才可能是最终根节点
构建映射：建立从根节点值到对应树的映射关系
递归合并：从最终根节点开始，递归地将子树合并进来。对于每个叶节点，如果其值对应某棵树的根节点，则用该树替换此叶节点
验证结果：检查最终树是否使用了所有原始树，并且是否为有效的二叉搜索树

复杂度优化：

使用哈希表快速查找对应的子树
通过入度统计快速找到根节点
递归过程中同时进行BST有效性检查

这种方法的时间复杂度主要取决于树的总节点数，空间复杂度为存储映射关系所需的空间。

代码实现

class Solution {
public:
    TreeNode* canMerge(vector<TreeNode*>& trees) {
        if (trees.size() == 1) return trees[0];
        
        unordered_map<int, TreeNode*> rootMap;
        unordered_map<int, int> leafCount;
        
        // 建立根节点映射并统计叶节点
        for (auto tree : trees) {
            rootMap[tree->val] = tree;
            if (tree->left) leafCount[tree->left->val]++;
            if (tree->right) leafCount[tree->right->val]++;
        }
        
        // 找到最终根节点（入度为0的根节点）
        TreeNode* finalRoot = nullptr;
        for (auto tree : trees) {
            if (leafCount[tree->val] == 0) {
                if (finalRoot) return nullptr; // 多个候选根节点
                finalRoot = tree;
            }
        }
        
        if (!finalRoot) return nullptr;
        
        // 递归合并
        unordered_set<TreeNode*> used;
        used.insert(finalRoot);
        
        function<void(TreeNode*)> merge = [&](TreeNode* node) {
            if (!node) return;
            
            if (node->left && rootMap.count(node->left->val) && !used.count(rootMap[node->left->val])) {
                TreeNode* subtree = rootMap[node->left->val];
                used.insert(subtree);
                node->left = subtree;
            }
            
            if (node->right && rootMap.count(node->right->val) && !used.count(rootMap[node->right->val])) {
                TreeNode* subtree = rootMap[node->right->val];
                used.insert(subtree);
                node->right = subtree;
            }
            
            merge(node->left);
            merge(node->right);
        };
        
        merge(finalRoot);
        
        // 检查是否使用了所有树
        if (used.size() != trees.size()) return nullptr;
        
        // 验证BST
        function<bool(TreeNode*, long, long)> isValidBST = [&](TreeNode* node, long minVal, long maxVal) -> bool {
            if (!node) return true;
            if (node->val <= minVal || node->val >= maxVal) return false;
            return isValidBST(node->left, minVal, node->val) && isValidBST(node->right, node->val, maxVal);
        };
        
        return isValidBST(finalRoot, LONG_MIN, LONG_MAX) ? finalRoot : nullptr;
    }
};

class Solution:
    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:
        if len(trees) == 1:
            return trees[0]
        
        root_map = {}
        leaf_count = defaultdict(int)
        
        # 建立根节点映射并统计叶节点
        for tree in trees:
            root_map[tree.val] = tree
            if tree.left:
                leaf_count[tree.left.val] += 1
            if tree.right:
                leaf_count[tree.right.val] += 1
        
        # 找到最终根节点（入度为0的根节点）
        final_root = None
        for tree in trees:
            if leaf_count[tree.val] == 0:
                if final_root:
                    return None  # 多个候选根节点
                final_root = tree
        
        if not final_root:
            return None
        
        # 递归合并
        used = {final_root}
        
        def merge(node):
            if not node:
                return
            
            if (node.left and node.left.val in root_map and 
                root_map[node.left.val] not in used):
                subtree = root_map[node.left.val]
                used.add(subtree)
                node.left = subtree
            
            if (node.right and node.right.val in root_map and 
                root_map[node.right.val] not in used):
                subtree = root_map[node.right.val]
                used.add(subtree)
                node.right = subtree
            
            merge(node.left)
            merge(node.right)
        
        merge(final_root)
        
        # 检查是否使用了所有树
        if len(used) != len(trees):
            return None
        
        # 验证BST
        def is_valid_bst(node, min_val, max_val):
            if not node:
                return True
            if node.val <= min_val or node.val >= max_val:
                return False
            return (is_valid_bst(node.left, min_val, node.val) and
                    is_valid_bst(node.right, node.val, max_val))
        
        return final_root if is_valid_bst(final_root, float('-inf'), float('inf')) else None

public class Solution {
    public TreeNode CanMerge(IList<TreeNode> trees) {
        if (trees.Count == 1) return trees[0];
        
        var rootMap = new Dictionary<int, TreeNode>();
        var leafCount = new Dictionary<int, int>();
        
        // 建立根节点映射并统计叶节点
        foreach (var tree in trees) {
            rootMap[tree.val] = tree;
            if (tree.left != null) {
                leafCount[tree.left.val] = leafCount.GetValueOrDefault(tree.left.val, 0) + 1;
            }
            if (tree.right != null) {
                leafCount[tree.right.val] = leafCount.GetValueOrDefault(tree.right.val, 0) + 1;
            }
        }
        
        // 找到最终根节点（入度为0的根节点）
        TreeNode finalRoot = null;
        foreach (var tree in trees) {
            if (!leafCount.ContainsKey(tree.val) || leafCount[tree.val] == 0) {
                if (finalRoot != null) return null; // 多个候选根节点
                finalRoot = tree;
            }
        }
        
        if (finalRoot == null) return null;
        
        // 递归合并
        var used = new HashSet<TreeNode> { finalRoot };
        
        void Merge(TreeNode node) {
            if (node == null) return;
            
            if (node.left != null && rootMap.ContainsKey(node.left.val) && !used.Contains(rootMap[node.left.val])) {
                var subtree = rootMap[node.left.val];
                used.Add(subtree);
                node.left = subtree;
            }
            
            if (node.right != null && rootMap.ContainsKey(node.right.val) && !used.Contains(rootMap[node.right.val])) {
                var subtree = rootMap[node.right.val];
                used.Add(subtree);
                node.right = subtree;
            }
            
            Merge(node.left);
            Merge(node.right);
        }
        
        Merge(finalRoot);
        
        // 检查是否使用了所有树
        if (used.Count != trees.Count) return null;
        
        // 验证BST
        bool IsValidBST(TreeNode node, long minVal, long maxVal) {
            if (node == null) return true;
            if (node.val <= minVal || node.val >= maxVal) return false;
            return IsValidBST(node.left, minVal, node.val) && IsValidBST(node.right, node.val, maxVal);
        }
        
        return IsValidBST(finalRoot, long.MinValue, long.MaxValue) ? finalRoot : null;
    }
}

var canMerge = function(trees) {
    if (trees.length === 1) return trees[0];
    
    const rootMap = new Map();
    const leafSet = new Set();
    
    for (let tree of trees) {
        rootMap.set(tree.val, tree);
        if (tree.left) leafSet.add(tree.left.val);
        if (tree.right) leafSet.add(tree.right.val);
    }
    
    let mainRoot = null;
    for (let tree of trees) {
        if (!leafSet.has(tree.val)) {
            if (mainRoot) return null;
            mainRoot = tree;
        }
    }
    
    if (!mainRoot) return null;
    
    function merge(node) {
        if (!node) return true;
        
        if (node.left && !node.left.left && !node.left.right) {
            if (rootMap.has(node.left.val) && rootMap.get(node.left.val) !== mainRoot) {
                node.left = rootMap.get(node.left.val);
                rootMap.delete(node.left.val);
            }
        }
        
        if (node.right && !node.right.left && !node.right.right) {
            if (rootMap.has(node.right.val) && rootMap.get(node.right.val) !== mainRoot) {
                node.right = rootMap.get(node.right.val);
                rootMap.delete(node.right.val);
            }
        }
        
        return merge(node.left) && merge(node.right);
    }
    
    merge(mainRoot);
    
    if (rootMap.size > 1) return null;
    
    function isValidBST(node, min, max) {
        if (!node) return true;
        if (node.val <= min || node.val >= max) return false;
        return isValidBST(node.left, min, node.val) && isValidBST(node.right, node.val, max);
    }
    
    return isValidBST(mainRoot, -Infinity, Infinity) ? mainRoot : null;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	值	说明
时间复杂度	O(n)	n为所有树的总节点数，需要遍历所有节点进行统计、合并和验证
空间复杂度	O(n)	需要存储根节点映射、叶节点统计和已使用树的集合

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析