合并多棵二叉搜索树

标签: 树 深度优先搜索 哈希表 二分查找 二叉树

难度: Hard

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

Submission

运行时间: 1292 ms

内存: 43.4 MB

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:
        # 创建一个集合，用于存储所有出现在二叉树中作为叶子的节点的值
        leaves = set()
        # 创建一个字典，用于存储以树的根节点的值为键，对应树为值的键值对
        candidates = dict()
        for tree in trees:
            # 遍历所有树，把所有的左右孩子节点的值加入叶子集合，同时记录根节点和树的映射
            if tree.left:
                leaves.add(tree.left.val)
            if tree.right:
                leaves.add(tree.right.val)
            candidates[tree.val] = tree
        
        # 这个变量用于在中序遍历过程中存储前一个节点的值，以检查二叉搜索树的有效性
        prev = float("-inf")
        
        # 定义中序遍历函数，用递归方式进行
        def dfs(tree: Optional[TreeNode]) -> bool:
            
            if not tree:
                return True
            
            # 如果当前节点是叶子节点，并且在候选树中，进行合并操作
            if not tree.left and not tree.right and tree.val in candidates:
                # 合并完成后，将树丛哈希映射中移除，以便于在遍历结束后判断是否所有树都被遍历过
                merged_tree = candidates.pop(tree.val)
                tree.left = merged_tree.left
                tree.right = merged_tree.right
            
            # 递归检查左子树，如果左子树不满足条件，返回False
            if not dfs(tree.left):
                return False

            # 再遍历当前节点
            nonlocal prev

            # 检查当前节点是否满足二叉搜索树的条件
            if tree.val <= prev:
                return False

            prev = tree.val
            # 递归检查右子树，如果右子树不满足条件，返回False
            return dfs(tree.right)
        
        # 从所有树中找到唯一一个可能的根节点，即它的值没有在叶子集合中出现过
        for tree in trees:
            if tree.val not in leaves:
                # 从候选树中移除根节点，避免重复合并
                candidates.pop(tree.val)
                # 如果中序遍历有严格单调性，并且所有树的根节点都被遍历到，说明可以构造二叉搜索树
                return tree if dfs(tree) and not candidates else None

        return None

Explain

题解的策略主要是将所有树的根节点和叶子节点分别存储，通过查找唯一的根节点，然后尝试合并其他树作为其叶子节点。利用中序遍历保证合并后的树仍为有效的二叉搜索树（BST）。具体步骤为：1. 存储所有可能的叶子节点和根节点到相应的集合和字典中。2. 通过中序遍历的方式检查并合并树，使用递归方法在遍历过程中不断尝试用其他树替换叶子节点。3. 检查最终合并后的树是否符合BST的条件并确保所有树都已合并。

时间复杂度: O(n)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def canMerge(self, trees: List[TreeNode]) -> Optional[TreeNode]:
        leaves = set()  # 存储作为叶子节点的值
        candidates = dict()  # 存储树的根节点值与树的映射
        for tree in trees:
            if tree.left:
                leaves.add(tree.left.val)
            if tree.right:
                leaves.add(tree.right.val)
            candidates[tree.val] = tree
        prev = float('-inf')  # 用于中序遍历的前一个节点值比较
        def dfs(tree: Optional[TreeNode]) -> bool:
            nonlocal prev
            if not tree:
                return True
            if not tree.left and not tree.right and tree.val in candidates:
                merged_tree = candidates.pop(tree.val)
                tree.left = merged_tree.left
                tree.right = merged_tree.right
            if not dfs(tree.left):
                return False
            if tree.val <= prev:
                return False
            prev = tree.val
            return dfs(tree.right)
        for tree in trees:
            if tree.val not in leaves:
                candidates.pop(tree.val)
                return tree if dfs(tree) and not candidates else None
        return None

Explore

在合并多棵二叉搜索树的问题中，区分根节点和叶子节点是关键。使用集合存储叶子节点的值能够快速判断一个节点是否可能被其他树合并（即判断一个值是否仅为叶子节点）。使用字典存储根节点则是为了能够快速通过根节点的值找到对应的树，这对于尝试将一棵树合并到另一棵树的指定位置是必需的。这种数据结构的选择使得算法能够迅速地进行根节点和叶子节点的查找和比对，提高了合并的效率，同时也便于在后续中序遍历过程中进行树的替换和验证。

中序遍历（Left, Root, Right）对于二叉搜索树（BST）特别有用，因为它可以按照升序访问所有节点。在这个问题中，使用中序遍历可以逐步访问树中的每个节点，并与之前访问的节点的值进行比较，以确保所有的节点都按照二叉搜索树的要求正确排序（即每个节点的值都应该大于前一个访问的节点的值）。这种遍历方式自然而然地验证了BST的性质，而且由于其递归的性质，易于在遍历过程中进行合并操作。

在二叉搜索树（BST）中，任意节点的左子树中的所有节点的值都应小于该节点的值，而右子树中的所有节点的值都应大于该节点的值。中序遍历的特点是，对于BST，它应当输出一个严格递增的值序列。因此，在中序遍历过程中，如果发现当前节点的值不大于前一个访问的节点的值，这意味着树的这部分不满足BST的性质，因此返回False。这一判断确保了在合并过程中，合并后的树依然保持BST的所有条件。