首页 > 代码库 > leetcode - Unique Binary Search Trees II

leetcode - Unique Binary Search Trees II

2024-07-09 04:14:44   217人阅读

题目：Unique Binary Search Trees II

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

 

这道题是Unique Binary Search Trees I的后续，可以先看看http://www.cnblogs.com/laihaiteng/p/3789279.html这个，思路上有相似的地方

个人思路：

1、还是从1-n逐个遍历，作为BST的根节点，左半部分作为根节点的左子树，右半部分作为根节点的右子树

2、递归函数返回从start到end的节点所能产生的不同的BST的集合，则把不同的左BST与右BST做一个乘积（或者说一一匹配），就是此时某个i（1-n中的某个数）作为根节点的BST的集合

代码：

 1 #include <stddef.h> 2 #include <vector> 3  4 using namespace std; 5  6 struct TreeNode 7 { 8     int val; 9     TreeNode *left;10     TreeNode *right;11     TreeNode(int x) : val(x), left(NULL), right(NULL) {}12 };13 14 class Solution15 {16 public:17     vector<TreeNode *> generateTrees(int n)18     {19         vector<TreeNode *> result;20 21         if (n < 1)22         {23             TreeNode *root = NULL;24             result.push_back(root);25             return result;26         }27 28         result = generatePartTrees(1, n);29 30         return result;31     }32 private:33     vector<TreeNode *> generatePartTrees(int start, int end)34     {35         vector<TreeNode *> part;36 37         for (int i = start; i <= end; ++i)38         {39             vector<TreeNode *> leftTrees = generatePartTrees(start, i - 1);40             vector<TreeNode *> rightTrees = generatePartTrees(i + 1, end);41             //左右子树非空42             if (!leftTrees.empty() && !rightTrees.empty())43             {44                 for (int x = 0; x < leftTrees.size(); ++x)45                 {46                     for (int y = 0; y < rightTrees.size(); ++y)47                     {48                         TreeNode *root = new TreeNode(i);49                         TreeNode *left = leftTrees[x];50                         root->left = left;51                         TreeNode *right = rightTrees[y];52                         root->right = right;53                         part.push_back(root);54                     }55                 }56             }57             //左子树非空，右子树为空58             if (!leftTrees.empty() && rightTrees.empty())59             {60                 for (int x = 0; x < leftTrees.size(); ++x)61                 {62                     TreeNode *root = new TreeNode(i);63                     TreeNode *left = leftTrees[x];64                     root->left = left;65                     root->right = NULL;66                     part.push_back(root);67                 }68             }69             //左子树为空，右子树非空70             if (leftTrees.empty() && !rightTrees.empty())71             {72                 for (int y = 0; y < rightTrees.size(); ++y)73                 {74                     TreeNode *root = new TreeNode(i);75                     TreeNode *right = rightTrees[y];76                     root->left = NULL;77                     root->right = right;78                     part.push_back(root);79                 }80             }81             //左右子树均为空82             if (leftTrees.empty() && rightTrees.empty())83             {84                 TreeNode *root = new TreeNode(i);85                 root->left = NULL;86                 root->right = NULL;87                 part.push_back(root);88             }89         }90 91         return part;92     }93 };
View Code

 

网上看了一下，大致都是这个思路，但发现有更好的写法，链接：http://www.cnblogs.com/remlostime/archive/2012/11/19/2777841.html

 

精简了一下代码：

 1 #include <stddef.h> 2 #include <vector> 3  4 using namespace std; 5  6 struct TreeNode 7 { 8     int val; 9     TreeNode *left;10     TreeNode *right;11     TreeNode(int x) : val(x), left(NULL), right(NULL) {}12 };13 14 class Solution15 {16 public:17     vector<TreeNode *> generateTrees(int n)18     {19         return generatePartTrees(1, n);20     }21 private:22     vector<TreeNode *> generatePartTrees(int start, int end)23     {24         vector<TreeNode *> part;25 26         if (start > end)27         {28             part.push_back(NULL);29             return part;30         }31 32         for (int i = start; i <= end; ++i)33         {34             vector<TreeNode *> leftTrees = generatePartTrees(start, i - 1);35             vector<TreeNode *> rightTrees = generatePartTrees(i + 1, end);36             for (int x = 0; x < leftTrees.size(); ++x)37             {38                 for (int y = 0; y < rightTrees.size(); ++y)39                 {40                     TreeNode *root = new TreeNode(i);41                     TreeNode *left = leftTrees[x];42                     root->left = left;43                     TreeNode *right = rightTrees[y];44                     root->right = right;45                     part.push_back(root);46                 }47             }48         }49 50         return part;51     }52 };
View Code

 


联系
我们