【力扣】[動态規劃] 95.不同的二叉搜尋樹 II

1、題目

給你一個整數 n ，請你生成并傳回所有由 n 個節點組成且節點值從 1 到 n 互不相同的不同 二叉搜尋樹 。可以按 任意順序 傳回答案。

連結： https://leetcode-cn.com/problems/unique-binary-search-trees-ii/

2、思路分析

1）回溯

我們定義 generateTrees(start, end) 函數表示目前值的集合為 [start,end]，傳回序列 [start,end] 生成的所有可行的二叉搜尋樹。

我們考慮枚舉 [start,end] 中的值 i 為目前二叉搜尋樹的根，那麼序列劃分為[start,i−1] 和[i+1,end] 兩部分。我們遞歸調用這兩部分，即 generateTrees(start, i - 1) 和 generateTrees(i + 1, end)，獲得所有可行的左子樹和可行的右子樹。

那麼最後一步我們隻要從可行左子樹集合中選一棵，再從可行右子樹集合中選一棵拼接到根節點上，并将生成的二叉搜尋樹放入答案數組即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int start, int end)
    {
        if(start > end){
            return {nullptr};
        }
        if(start == end){
            return {new TreeNode(start)};
        }
        vector<TreeNode*> res;
        for(int i = start; i <= end; ++i){
            // 左子樹集合
            vector<TreeNode*> left = generateTrees(start, i - 1);
            vector<TreeNode*> right = generateTrees(i + 1, end);
            for(auto & l :left){
                for(auto& r : right){
                    res.push_back(new TreeNode(i, l, r));
                }
            }
        }
        return res;
    }

    vector<TreeNode*> generateTrees(int n) {
        return generateTrees(1, n);
    }
};