Unique Binary Search Trees II

逃离我推掉我的手 2021-11-17 04:10 176阅读 0赞

Given an integer  *n*, generate all structurally unique BST's (binary search trees) that store values 1 ...  *n*.

Example:
    
    Input: 3
    Output:
    [
      [1,null,3,2],
      [3,2,null,1],
      [3,1,null,null,2],
      [2,1,3],
      [1,null,2,null,3]
    ]
    Explanation:
    The above output corresponds to the 5 unique BST's shown below:
    
       1         3     3      2      1
        \       /     /      / \      \
         3     2     1      1   3      2
        /     /       \                 \
       2     1         2                 3

code

class Solution
    {
    public:
        vector<TreeNode*> generateTrees(int n)
        {
            if(n<=0)
                return {};
    
            return generateTreesCore(1,n);
        }
    private:
        vector<TreeNode *> generateTreesCore(int start,int end)
        {
            if(start==end)
                return {
         new TreeNode(start)};
            else if(start>end)
                return {nullptr};
    
            vector<TreeNode *> res;
            for(int i=start;i<=end;++i)
            {
                auto left=generateTreesCore(start,i-1);
                auto right=generateTreesCore(i+1,end);
    
                for(auto &l:left)
                {
                    for(auto &r:right)
                    {
                        TreeNode *t=new TreeNode(i);
                        t->left=l;
                        t->right=r;
                        res.emplace_back(t);
                    }
                }
            }
            return res;
        }
    };

转载于:https://www.cnblogs.com/tianzeng/p/10957110.html

发表评论取消回复

表情：

评论列表（有 0 条评论，176人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - Medium - 95. Unique Binary Search Trees II

Topic Dynamic Programming Tree Description [https://leetcode.com/problems/u

比眉伴天荒/ 2022年10月06日 06:58/ 0 赞/ 56 阅读

相关 leetcode 95. Unique Binary Search Trees II | 96. Unique Binary Search Trees

95. Unique Binary Search Trees II [https://leetcode.com/problems/unique-binary-search

布满荆棘的人生/ 2022年09月10日 03:13/ 0 赞/ 171 阅读

相关 LeetCode95—Unique Binary Search Trees II

LeetCode95—Unique Binary Search Trees II 分治法求解结构不同BST（查找二叉树）原题 > Given n, genera

阳光穿透心脏的1/2处/ 2022年08月21日 01:27/ 0 赞/ 8 阅读

相关 Unique Binary Search Trees II--LeetCode

题目： Given n, generate all structurally unique BST's (binary search trees) that sto

矫情吗；*/ 2022年08月05日 14:18/ 0 赞/ 149 阅读

相关 Unique Binary Search Trees--LeetCode

题目： Given n, how many structurally unique BST's (binary search trees) that store valu

ゞ浴缸里的玫瑰/ 2022年08月05日 14:18/ 0 赞/ 171 阅读

相关 [leetcode]95. Unique Binary Search Trees II

题目链接：[95. Unique Binary Search Trees II][] Given an integer n, generate all structurall

左手的ㄟ右手/ 2022年07月21日 02:22/ 0 赞/ 175 阅读

相关 [Leetcode][python]Unique Binary Search Trees II

题目大意给出一个n，求1-n能够得到的所有二叉搜索树，输出所有树解题思路递归拼接树该题较难，参考[题解][Link 1]的思路。从start到end

喜欢ヅ旅行/ 2022年06月11日 04:11/ 0 赞/ 142 阅读

相关 96. Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1 ..

小鱼儿/ 2022年03月07日 01:14/ 0 赞/ 148 阅读

相关 Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...

刺骨的言语ヽ痛彻心扉/ 2021年12月17日 10:29/ 0 赞/ 235 阅读

相关 Unique Binary Search Trees II

Given an integer n, generate all structurally unique BST's (binary search trees) that s

逃离我推掉我的手/ 2021年11月17日 04:10/ 0 赞/ 177 阅读