不同的二叉搜索树 II

难度:

标签:

题目描述

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

示例 1：

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

示例 2：

输入：n = 1
输出：[[1]]

提示：

1 <= n <= 8

代码结果

运行时间: 60 ms, 内存: 16.8 MB

/*
 * 思路：
 * 1. 使用Stream API生成所有可能的二叉搜索树。
 * 2. 主要使用flatMap和map来生成所有的树节点组合。
 */
 
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
 
// 树节点定义
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
 
public class UniqueBSTStream {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) return new ArrayList<>();
        return generateTreesHelper(1, n);
    }
 
    private List<TreeNode> generateTreesHelper(int start, int end) {
        if (start > end) {
            return List.of((TreeNode) null);
        }
 
        return IntStream.rangeClosed(start, end)
                .boxed()
                .flatMap(i -> {
                    List<TreeNode> leftTrees = generateTreesHelper(start, i - 1);
                    List<TreeNode> rightTrees = generateTreesHelper(i + 1, end);
                    return leftTrees.stream()
                            .flatMap(left -> rightTrees.stream()
                                    .map(right -> {
                                        TreeNode currentTree = new TreeNode(i);
                                        currentTree.left = left;
                                        currentTree.right = right;
                                        return currentTree;
                                    }));
                })
                .collect(Collectors.toList());
    }
}

解释

方法:

这个题解使用递归的方法来生成所有可能的二叉搜索树。主要思路是：对于从1到n的每个数i，将其作为根节点，然后递归生成所有可能的左子树（由小于i的数组成）和右子树（由大于i的数组成），最后将左右子树与根节点i组合起来，形成一棵完整的二叉搜索树。通过遍历1到n的每个数作为根节点，可以生成所有可能的二叉搜索树。

时间复杂度:

O(4^n / n^(3/2))

空间复杂度:

O(4^n / n^(3/2))

代码细节讲解

🦆

为什么在递归函数中，当start大于end时，返回的是包含None的列表而不是空列表？

▷

在递归函数中，当start大于end时，返回包含None的列表而不是空列表的原因是为了表示该子树为空。这样做是因为在构建二叉搜索树时，我们需要一个明确的表示方式来指示没有子节点的情况。如果返回空列表，那么在后续的循环中将无法正确地进行左右子树的组合，因为我们需要一个占位符来表示树的这一部分不存在。通过返回包含None的列表，我们能确保每个可能的树结构都被考虑和构建，包括那些具有空子树的结构。

🦆

递归生成左右子树时，如何保证生成的子树满足二叉搜索树的性质？

▷

在递归生成左右子树时，保证生成的子树满足二叉搜索树(BST)的性质是通过选择的根节点和递归调用的范围来控制的。对于每个数i，当它被选择为根节点时，我们递归地生成所有小于i的数作为它的左子树，所有大于i的数作为右子树。这是通过调用递归函数helper(start, i-1)来生成左子树，和调用helper(i+1, end)来生成右子树实现的。这样的递归分割确保了左子树中所有的值都小于根节点，而右子树中所有的值都大于根节点，从而满足BST的性质。

🦆

在递归过程中，是否有可能通过缓存或其他方式优化重复计算？

▷

在递归过程中，确实可以通过缓存（也称为记忆化）来优化重复计算。由于生成二叉搜索树的函数可能会多次计算相同范围的子树，我们可以使用一个缓存来存储这些子树的结果。具体做法是使用一个字典或数组来保存从start到end范围内生成的所有可能的二叉搜索树。在递归函数开始时，我们首先检查缓存中是否已经存储了当前范围的结果，如果有，直接返回这些结果；如果没有，继续计算并在计算结束后将结果存入缓存。这种方法可以显著减少重复的计算量，提高算法的效率。

相关问题