LeetCode 0095 - Unique Binary Search Trees II
# Hints
DP
记忆化搜索
# 前置题目
LeetCode 0096 - Unique Binary Search Trees
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given an integer , return all the structurally unique BST's (binary search trees), which has exactly nodes of unique values from to . Return the answer in any order.
Example 1:
Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
Example 2:
Input: n = 1
Output: [[1]]
Constraints:
# 题意
给定一个正整数 ,求由键值为 的 个节点组成的二叉查找树的所有可能的结构。返回的结果可按任意顺序排列。
# 题解
根据 LeetCode 0096 的解法进行记忆化搜索即可。本题数据范围小,无需记忆化直接暴力 DFS 也能通过。
# AC代码
/**
* 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 {
private:
typedef vector<TreeNode *> vectrees;
private:
static const int MAXN = 8 + 1;
vectrees dp[MAXN][MAXN];
public:
vectrees generateTrees(int n) {
return dfs(1, n);
}
// 深度优先搜索
vectrees dfs(int left, int right) {
// 递归终止
if (left > right) {
return vectrees({nullptr});
}
if (!dp[left][right].empty()) {
return dp[left][right];
}
// 递归
vectrees curtrees;
for (int i = left; i <= right; i ++) {
vectrees ltrees = dfs(left, i - 1);
vectrees rtrees = dfs(i + 1, right);
for (auto l : ltrees) for (auto r : rtrees) {
TreeNode * root = new TreeNode(i, l, r);
curtrees.push_back(root);
}
}
// 返回
dp[left][right] = curtrees;
return dp[left][right];
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01