Medium

题目描述

给你一个整数 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

解题思路

这道题要求生成所有可能的二叉搜索树，是一个典型的递归分治问题。

核心思路： 对于给定范围 [start, end]，我们可以选择其中任意一个数字 i 作为根节点，那么：

  • 左子树包含 [start, i-1] 范围内的所有数字
  • 右子树包含 [i+1, end] 范围内的所有数字

由于二叉搜索树的性质，左子树的所有值都小于根节点，右子树的所有值都大于根节点，这样的划分是合理的。

递归过程：

  1. 如果 start > end，返回包含 null 的列表
  2. 遍历 [start, end] 中的每个数字 i 作为根节点
  3. 递归生成所有可能的左子树和右子树
  4. 将每种左子树和右子树的组合与当前根节点组合，形成完整的树

优化方案： 可以使用记忆化搜索来避免重复计算相同范围的子问题，但由于 n ≤ 8，直接递归也足够高效。

这种方法时间复杂度较高，但能生成所有可能的结构不同的二叉搜索树。

代码实现

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        return generateTrees(1, n);
    }
    
private:
    vector<TreeNode*> generateTrees(int start, int end) {
        if (start > end) {
            return {nullptr};
        }
        
        vector<TreeNode*> result;
        for (int i = start; i <= end; i++) {
            vector<TreeNode*> leftTrees = generateTrees(start, i - 1);
            vector<TreeNode*> rightTrees = generateTrees(i + 1, end);
            
            for (TreeNode* left : leftTrees) {
                for (TreeNode* right : rightTrees) {
                    TreeNode* root = new TreeNode(i);
                    root->left = left;
                    root->right = right;
                    result.push_back(root);
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        def generateTrees(start, end):
            if start > end:
                return [None]
            
            result = []
            for i in range(start, end + 1):
                left_trees = generateTrees(start, i - 1)
                right_trees = generateTrees(i + 1, end)
                
                for left in left_trees:
                    for right in right_trees:
                        root = TreeNode(i)
                        root.left = left
                        root.right = right
                        result.append(root)
            
            return result
        
        return generateTrees(1, n)

public class Solution {
    public IList<TreeNode> GenerateTrees(int n) {
        return GenerateTrees(1, n);
    }
    
    private IList<TreeNode> GenerateTrees(int start, int end) {
        if (start > end) {
            return new List<TreeNode> { null };
        }
        
        var result = new List<TreeNode>();
        for (int i = start; i <= end; i++) {
            var leftTrees = GenerateTrees(start, i - 1);
            var rightTrees = GenerateTrees(i + 1, end);
            
            foreach (var left in leftTrees) {
                foreach (var right in rightTrees) {
                    var root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    result.Add(root);
                }
            }
        }
        
        return result;
    }
}

var generateTrees = function(n) {
    function generateTreesHelper(start, end) {
        if (start > end) {
            return [null];
        }
        
        const result = [];
        for (let i = start; i <= end; i++) {
            const leftTrees = generateTreesHelper(start, i - 1);
            const rightTrees = generateTreesHelper(i + 1, end);
            
            for (const left of leftTrees) {
                for (const right of rightTrees) {
                    const root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    result.push(root);
                }
            }
        }
        
        return result;
    }
    
    return generateTreesHelper(1, n);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(G(n))，其中 G(n) 是第 n 个卡特兰数，约为 O(4^n/n^(3/2))
空间复杂度O(G(n))，需要存储所有生成的树节点

相关题目