合并多棵二叉搜索树
难度:
标签:
题目描述
给你 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.length1 <= n <= 5 * 104- 每棵树中节点数目在范围
[1, 3]内。 - 输入数据的每个节点可能有子节点但不存在子节点的子节点
trees中不存在两棵树根节点值相同的情况。- 输入中的所有树都是 有效的二叉树搜索树 。
1 <= TreeNode.val <= 5 * 104.
代码结果
运行时间: 1292 ms, 内存: 43.4 MB
/*
* 思路：
* 1. 使用 Java Stream API 遍历和操作树列表。
* 2. 将每个树的根节点和叶子节点存储在映射中。
* 3. 使用流操作找到可以合并的树，并执行合并操作。
* 4. 返回最终的根节点或null。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public TreeNode canMerge(List<TreeNode> trees) {
Map<Integer, TreeNode> rootMap = trees.stream().collect(Collectors.toMap(t -> t.val, t -> t));
Map<Integer, TreeNode> leafMap = trees.stream()
.flatMap(t -> Stream.of(t.left, t.right))
.filter(Objects::nonNull)
.collect(Collectors.toMap(l -> l.val, l -> rootMap.get(l.val)));
trees.forEach(tree -> {
if (leafMap.containsKey(tree.val)) {
TreeNode parent = leafMap.get(tree.val);
if (parent.left != null && parent.left.val == tree.val) parent.left = tree;
if (parent.right != null && parent.right.val == tree.val) parent.right = tree;
rootMap.remove(tree.val);
}
});
return rootMap.size() == 1 && isValidBST(rootMap.values().iterator().next(), null, null) ? rootMap.values().iterator().next() : null;
}
private boolean isValidBST(TreeNode node, Integer low, Integer high) {
if (node == null) return true;
if ((low != null && node.val <= low) || (high != null && node.val >= high)) return false;
return isValidBST(node.left, low, node.val) && isValidBST(node.right, node.val, high);
}
}
解释
方法:
题解的策略主要是将所有树的根节点和叶子节点分别存储，通过查找唯一的根节点，然后尝试合并其他树作为其叶子节点。利用中序遍历保证合并后的树仍为有效的二叉搜索树（BST）。具体步骤为：1. 存储所有可能的叶子节点和根节点到相应的集合和字典中。2. 通过中序遍历的方式检查并合并树，使用递归方法在遍历过程中不断尝试用其他树替换叶子节点。3. 检查最终合并后的树是否符合BST的条件并确保所有树都已合并。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在解题策略中，为何需要将所有可能的叶子节点存储在一个集合中，而根节点则存储在字典中？这种数据结构的选择对算法有何影响？
▷🦆
题解中提到使用递归方法中序遍历进行树的合并检查，为何选择中序遍历而非其他类型的遍历方式？中序遍历在这个问题中有什么特别的优势？
▷🦆
题解中提到如果中序遍历过程中发现当前节点的值不大于前一个节点的值，则返回False。这个判断条件是如何保证BST属性的？
▷