链接
https://leetcode-cn.com/problems/unique-binary-search-trees-ii/
耗时
解题:0.5 day
题解:36 min
题意
给定一个整数 n,生成所有由 1 … n 为节点所组成的 二叉搜索树 。
思路
和 【leetcode】96. 不同的二叉搜索树(unique-binary-search-trees)(DP)[中等] 是一样的思路,当左子树有 0~n-1 个节点时,根据之前的二叉搜索树求出左右子树的所有可能,只不过 96. 是求种数,本题需要给出具体的二叉搜索树 。
值得注意的是,在遍历左右子树可能出现的情况时,右子树不能直接使用之前的二叉树,因为数值不符,当左子树有 j 个节点时,当前的根节点应该是 j+1,所以右子树的所有数值都加上 j+1 即可。然而不能直接在原位置加,否则之后就没法用了,解决方法是:dfs 新建一个相同的树,在建树的同时加上 j+1 即可。
时间复杂度:
O
(
?
)
O(?)
O(?)
AC代码
class Solution {
public:
TreeNode* dfs(TreeNode *&root, int offset) {
if(root == NULL) return NULL;
TreeNode *res = new TreeNode(root->val+offset);
res->left = dfs(root->left, offset);
res->right = dfs(root->right, offset);
return res;
}
vector<TreeNode*> generateTrees(int n) {
if(n == 0) return {};
vector<vector<TreeNode*>> ans(n+1);
ans[0].push_back(NULL);
ans[1].push_back(new TreeNode(1));
for(int i = 2; i <= n; ++i) {
for(int j = 0; j < i; ++j) {
for(int k = 0; k < ans[j].size(); ++k) {
for(int o = 0; o < ans[i-1-j].size(); ++o) {
TreeNode *l = ans[j][k];
TreeNode *r = dfs(ans[i-1-j][o], j+1);
TreeNode *tmp = new TreeNode(j+1, l, r);
ans[i].push_back(tmp);
}
}
}
}
return ans[n];
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)