欢迎访问LeetCode题解合集
题目描述
给定一个整数 n,生成所有由 1 … n 为节点所组成的 二叉搜索树 。
示例:
输入:3
输出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
提示:
- $0 \le n \le 8$
题解:
递归。
对连续的区间 [l, r]
,枚举二叉搜索树的根节点,假设当前为 i
:
- 分别递归求左右子树的所有方案
[l, i - 1]
和[i + 1, r]
- 左子树的任意一种方案可以和右子树的任意一种方案拼接在一起,以
i
为根节点即可组成区间[l, r]
上的一棵二叉搜索树
时间复杂度:$O(n \times \frac{4^n}{n^{\frac{3}{2}}})$ = $O(\frac{4^n}{\sqrt{n}})$
额外空间复杂度:$O(n)$
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<TreeNode*> dfs( int l, int r ) {
if ( l > r ) return { nullptr };
vector<TreeNode*> ret;
for ( int i = l; i <= r; ++i ) {
vector<TreeNode*> left = dfs( l, i - 1 );
vector<TreeNode*> right = dfs( i + 1, r );
for ( auto& l : left ) {
for ( auto& r : right ) {
TreeNode *root = new TreeNode( i, l, r );
ret.emplace_back( root );
}
}
}
return ret;
}
vector<TreeNode*> generateTrees(int n) {
if (!n) return {};
return dfs( 1, n );
}
};
/*
时间:24ms,击败:81.22%
内存:15.8MB,击败:68.00%
*/
可以记忆化优化搜索优化一下:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<vector<TreeNode*>> > f;
vector<TreeNode*> dfs( int l, int r ) {
if ( l > r ) return { nullptr };
if ( f[l][r].size() ) return f[l][r];
vector<TreeNode*> ret;
for ( int i = l; i <= r; ++i ) {
vector<TreeNode*> left = dfs( l, i - 1 );
vector<TreeNode*> right = dfs( i + 1, r );
for ( auto& l : left ) {
for ( auto& r : right ) {
TreeNode *root = new TreeNode( i, l, r );
ret.emplace_back( root );
}
}
}
return f[l][r] = ret;
}
vector<TreeNode*> generateTrees(int n) {
if (!n) return {};
f = vector<vector<vector<TreeNode*>>>(n + 1, vector<vector<TreeNode*>>(n + 1));
return dfs( 1, n );
}
};
/*
时间:16ms,击败:98.28%
内存:12.1MB,击败:98.91%
*/
说明确实出现很多重复的子区间,虽然额外的开辟了一个记忆化数组,但是减少了重复子区间需要的临时堆栈内存。