Unique Binary Search Trees II--LeetCode

矫情吗；* 2022-08-05 14:18 135阅读 0赞

# 题目： #

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

For example,  
Given n = 3, your program should return all 5 unique BST's shown below.

1         3     3      2      1
        \       /     /      / \      \
         3     2     1      1   3      2
        /     /       \                 \
       2     1         2                 3

从思路上来说，我们以任意一个数值作为根节点，左边的数构成所有的左子树，右边的树构成右子树，然后然后左右子树任意组合，之后构成当前节点为根的所有树。思路是每次一次选取一个结点为根，然后递归求解左右子树的所有结果，最后根据左右子树的返回的所有子树，依次选取然后接上（每个左边的子树跟所有右边的子树匹配，而每个右边的子树也要跟所有的左边子树匹配，总共有左右子树数量的乘积种情况），构造好之后作为当前树的结果返回。

vector<TreeNode *> generateTrees(int n) {  
           return createTree(1,n);  
        }  
          
        vector<TreeNode *> createTree(int start, int end)  
        {  
            vector<TreeNode *> results;  
            if(start>end)  
            {  
                results.push_back(NULL);  
                return results;  
            }  
              
            for(int k=start;k<=end;k++)  
            {  
                vector<TreeNode *> left = createTree(start,k-1);  
                vector<TreeNode *> right = createTree(k+1,end);  
                for(int i=0;i<left.size();i++)  
                {  
                    for(int j=0;j<right.size();j++)  
                    {  
                        TreeNode * root = new TreeNode(k);  
                        root->left = left[i];  
                        root->right = right[j];  
                        results.push_back(root);  
                    }  
                }  
            }  
            return results;  
        }