leetcode刷题笔记-95.不同的二叉搜索树2

95.不同的二叉搜索树2

https://leetcode.cn/problems/unique-binary-search-trees-ii/description/

题目

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

思路

这道题需要在96题的基础上，构造这些不同的二叉树并返回。

乍一看好像是一个回溯的思路，但个人感觉更像是一个普通的分治递归，回溯的思想体现的不是很明显。

首先基本的想法还是要把这个树进行拆分，可以用区间作为递归函数的参数，区间越界的时候就返回。

在那之前，我们需要确定递归的返回值。注意本题的返回值是一个vector<TreeNode*>数组，而且并不能套用回溯题中在递归返回时插入结果集的思路，那样是在叶子节点插入，而本题需要的是根节点。

所以我们应该直接用vector<TreeNode*>作为递归函数的返回值，在每一层的循环结束后返回这个数组。数组值的含义是以本层区间为根节点，可以得到的不同子树集合。

1	vector<TreeNode*> curTree; // 当前层可能的树的集合

确定了返回值，就可以写出递归的终止条件了，区间不合法的时候，返回一个包含nullptr的空数组。即代表空节点。

// 两个区间越界，返回空
if (begin > end) {
    return {nullptr};
}

在每一层循环中，我们尝试使用begin和end中的任意一个节点作为二叉搜索树的根节点，然后递归遍历左区间和右区间，构造符合条件的子树数组。

for (int i = begin; i <= end; i++) {
	// 递归左右区间，注意begin和end都是闭区间，应该跳过i自己
	vector<TreeNode*> leftTree = _generateTrees(begin, i - 1);
    vector<TreeNode*> rightTree = _generateTrees(i + 1, end);
}

然后再将得到的子树数组拼起来。此时拼起来的树就可以插入当前层的完整树数组中了

// 遍历左右子树，构造可能的树的集合
// 如果是叶子节点，此时left和right应该都是一个{nullptr}
for (auto& left : leftTree) {
	for (auto& right : rightTree) {
		// 直接用构造函数传参
		TreeNode* root = new TreeNode(i, left, right);
		curTree.push_back(root);
	}
}

最后循环终止，将得到的curTree数组返回。

代码

完整代码如下。

class Solution {
    vector<TreeNode*> _generateTrees(int begin, int end) {
        // 两个区间越界，返回空
        if (begin > end) {
            return {nullptr};
        }
        vector<TreeNode*> curTree; // 当前层可能的树的集合
        for (int i = begin; i <= end; i++) {
            // 获取左右子树的可能的树的集合，而不是单个树（递归子区间的树集合，直到空节点）
            vector<TreeNode*> leftTree = _generateTrees(begin, i - 1);
            vector<TreeNode*> rightTree = _generateTrees(i + 1, end);
            // 遍历左右子树，构造可能的树的集合
            // 如果是叶子节点，此时left和right应该都是一个{nullptr}
            for (auto& left : leftTree) {
                for (auto& right : rightTree) {
                    // 直接用构造函数传参
                    TreeNode* root = new TreeNode(i, left, right);
                    curTree.push_back(root);
                }
            }
        }
        // 返回给上一层
        return curTree;
    }

public:
    vector<TreeNode*> generateTrees(int n) {
        // 递归生成1到n的树
        return _generateTrees(1, n);
    }
};