首页 > 代码库 > Leetcode#95 Unique Binary Search Trees II
Leetcode#95 Unique Binary Search Trees II
原题地址
Unique Binary Search Trees（参见这篇文章）的升级版
做题的时候我在想，这要是把每个二叉树都独立创建一份得多麻烦啊，试试能不能共用"公共部分"，试了一下，果然可以，哈哈。
trees[i][j]表示数字i到j所能组成的所有二叉树的根节点
代码：
1 vector<TreeNode *> generateTrees(int n) { 2 if (n < 1) 3 return vector<TreeNode *>(1, NULL); 4 5 vector<vector<vector<TreeNode *> > > trees(n + 1, vector<vector<TreeNode *> >(n + 1, vector<TreeNode *>())); 6 7 for (int len = 1; len <= n; len++) { 8 for (int i = 1, j = i + len - 1; j <= n; i++, j++) { 9 for (int k = i; k <= j; k++) {10 vector<TreeNode *> lefts = k == i ? vector<TreeNode *>(1, NULL) : trees[i][k - 1];11 vector<TreeNode *> rights = k == j ? vector<TreeNode *>(1, NULL) : trees[k + 1][j];12 for (auto l : lefts) {13 for (auto r : rights) {14 TreeNode *node = new TreeNode(k);15 node->left = l;16 node->right = r;17 trees[i][j].push_back(node);18 }19 }20 }21 }22 }23 24 return trees[1][n];25 }
Leetcode#95 Unique Binary Search Trees II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。