Comment on page
0095. 不同的二叉搜索树 II
给定一个整数 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
- 二叉搜索树
- 分治
- 阿里
- 腾讯
- 百度
- 字节
只是我们需要求解的不仅仅是数字，而是要求解所有的组合。我们假设问题 f(1, n) 是求解 1 到 n（两端包含）的所有二叉树。那么我们的目标就是求解 f(1, n)。
我们将问 题进一步划分为子问题，假如左侧和右侧的树分别求好了，我们是不是只要运用组合的原理，将左右两者进行合并就好了，我们需要两层循环来完成这个过程。
- 分治法
语言支持：Python3, CPP
Python3 Code:
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
if not n:
return []
def generateTree(start, end):
if start > end:
return [None]
res = []
for i in range(start, end + 1):
ls = generateTree(start, i - 1)
rs = generateTree(i + 1, end)
for l in ls:
for r in rs:
node = TreeNode(i)
node.left = l
node.right = r
res.append(node)
return res
return generateTree(1, n)
CPP Code:
class Solution {
private:
vector<TreeNode*> generateTrees(int first, int last) {
if (first > last) return { NULL };
vector<TreeNode*> v;
for (int i = first; i <= last; ++i) {
auto lefts = generateTrees(first, i - 1);
auto rights = generateTrees(i + 1, last);
for (auto left : lefts) {
for (auto right : rights) {
v.push_back(new TreeNode(i));
v.back()->left = left;
v.back()->right = right;
}
}
}
return v;
}
public:
vector<TreeNode*> generateTrees(int n) {
if (n <= 0) return {};
return generateTrees(1, n);
}
};
复杂度分析 令 C(N) 为 N 的卡特兰数。
- 时间复杂度：$O(N*C(N))$
- 空间复杂度：$O(C(N))$
最近更新 2yr ago