leetcode 95. 不同的二叉搜索树 II（C++）

我不是女神ヾ 2023-07-18 02:33 15阅读 0赞

# 题目 #

给定一个整数 n，生成所有由 1 … n 为节点所组成的二叉搜索树。

示例:

输入: 3
    输出:
    [
      [1,null,3,2],
      [3,2,null,1],
      [3,1,null,null,2],
      [2,1,3],
      [1,null,2,null,3]
    ]
    解释:
    以上的输出对应以下 5 种不同结构的二叉搜索树：
    
       1         3     3      2      1
        \       /     /      / \      \
         3     2     1      1   3      2
        /     /       \                 \
       2     1         2                 3

来源：[95. 不同的二叉搜索树 II - 力扣（LeetCode）][95. _ II - _LeetCode]  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

以下思路来自：  
[详细通俗的思路分析，多解法 - 不同的二叉搜索树 II - 力扣（LeetCode）][- _ II - _LeetCode]  
作者：windliang

# 递归法 #

*  所以如果求 1…n 的所有可能。  
    我们只需要把 1 作为根节点，\[ \] 空作为左子树，\[ 2 … n \] 的所有可能作为右子树。  
    2 作为根节点，\[ 1 \] 作为左子树，\[ 3…n \] 的所有可能作为右子树。  
    3 作为根节点，\[ 1 2 \] 的所有可能作为左子树，\[ 4 … n \] 的所有可能作为右子树，然后左子树和右子树两两组合。  
    4 作为根节点，\[ 1 2 3 \] 的所有可能作为左子树，\[ 5 … n \] 的所有可能作为右子树，然后左子树和右子树两两组合。  
    …  
    n 作为根节点，\[ 1… n \] 的所有可能作为左子树，\[ \] 作为右子树。  
    至于，\[ 2 … n \] 的所有可能以及 \[ 4 … n \] 以及其他情况的所有可能，可以利用上边的方法，把每个数字作为根节点，然后把所有可能的左子树和右子树组合起来即可。  
    如果只有一个数字，那么所有可能就是一种情况，把该数字作为一棵树。而如果是 \[ \]，那就返回 null。

代码如下：

class Solution { 
    public:
        vector<TreeNode*> generateTrees(int n) { 
            vector<TreeNode*> ans{ };
            if(!n)  return ans;
            return igenerateTrees(1, n);
        }
    private:
        vector<TreeNode*> igenerateTrees(int start, int end){ 
            vector<TreeNode*> ans{ };
            if(start > end) ans.push_back(nullptr);
            for(int i = start;i <= end;i++){ 
                vector<TreeNode*> ltrees = igenerateTrees(start, i - 1);
                vector<TreeNode*> rtrees = igenerateTrees(i + 1, end);
                for(auto l : ltrees){ 
                    for(auto r : rtrees){ 
                        TreeNode* root = new TreeNode(i);
                        root->left = l;
                        root->right = r;
                        ans.push_back(root);
                    }
                }
            }
            return ans;
        }
    };

结果：  
![在这里插入图片描述][20200323234937845.png]

[95. _ II - _LeetCode]: https://leetcode-cn.com/problems/unique-binary-search-trees-ii
[- _ II - _LeetCode]: https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-2-7/
[20200323234937845.png]: /images/20230528/a3458507404b4b50a32ed11d809ae894.png