博文中会简要介绍Leetcode P0095题目分析及解题思路。
“Unique Binary Search Trees II”是一道非常有意思的题目，这道题有两种主流解法，一种是递归（回溯法），第二种是动态规划。本人才学有限，只能想到递归解法。
动态规划解法的思路十分精彩，不仅如此，就连动态规划也有两种不同的思路，简而言之，这篇文章里会记录递归解法，即回溯法，同时会记录一种思维更加直接明了的动态规划，另一种神仙解法就留给大家到Leetcode讨论区去学习了，
Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.
回溯法
回溯法的思路很直接明了，一共有n个结点，每个结点都可以作为根结点。小于这个根结点的所有值组成了左子树，大于这个根结点的所有值组成了右子树，然后左右递归之。
以下是Java的题解代码实现。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<TreeNode> generateTrees(int n) {
if (n == 0)
return new ArrayList<>();
return this.dfs(1, n);
}
private List<TreeNode> dfs(int begin, int end) {
List<TreeNode> subtrees = new ArrayList<>();
if (begin > end) {
subtrees.add(null);
return subtrees;
}
// Pruning
if (begin == end) {
subtrees.add(new TreeNode(begin));
return subtrees;
}
for (int rootVal=begin; rootVal<=end; ++rootVal) {
List<TreeNode> leftSubtrees = this.dfs(begin, rootVal-1);
List<TreeNode> rightSubtrees = this.dfs(rootVal+1, end);
for (TreeNode left: leftSubtrees) {
for (TreeNode right: rightSubtrees) {
TreeNode root = new TreeNode(rootVal);
root.left = left;
root.right = right;
subtrees.add(root);
}
}
}
return subtrees;
}
}
以下是C++的题解代码实现。
/**
* 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*> generateTrees(int n) {
if (n == 0)
return vector<TreeNode*>();
return this->Dfs(1, n);
}
private:
vector<TreeNode*> Dfs(const int begin, const int end) {
vector<TreeNode*> subtrees;
if (begin > end) {
subtrees.push_back(NULL);
return subtrees;
}
// Pruning
if (begin == end) {
subtrees.push_back(new TreeNode(begin));
return subtrees;
}
// DFS
for (int val=begin; val<=end; ++val) {
vector<TreeNode*> left_subtrees = this->Dfs(begin, val-1);
vector<TreeNode*> right_subtrees = this->Dfs(val+1, end);
for (TreeNode *left: left_subtrees) {
for (TreeNode *right: right_subtrees) {
TreeNode *root = new TreeNode(val);
root->left = left;
root->right = right;
subtrees.push_back(root);
}
}
}
return subtrees;
}
};
动态规划
这个动态规划思路相对好理解一些，它从二叉搜索树的性质入手，来进行记忆化的优化。以下解法参考了Leetcode博主windiang的博文。
考虑 [] 的所有解
null
考虑 [ 1 ] 的所有解
1
考虑 [ 1 2 ] 的所有解
2
/
1
1
\
2
考虑 [ 1 2 3 ] 的所有解
3
/
2
/
1
2
/ \
1 3
3
/
1
\
2
1
\
3
/
2
1
\
2
\
3
仔细分析，可以发现一个规律。首先我们每次新增加的数字大于之前的所有数字，所以新增加的数字出现的位置只可能是根节点或者是根节点的右孩子，右孩子的右孩子，右孩子的右孩子的右孩子等等，总之一定是右边。其次，新数字所在位置原来的子树，改为当前插入数字的左孩子即可，因为插入数字是最大的。
对于下边的解
2
/
1
然后增加 3
1.把 3 放到根节点
3
/
2
/
1
2. 把 3 放到根节点的右孩子
2
/ \
1 3
对于下边的解
1
\
2
然后增加 3
1.把 3 放到根节点
3
/
1
\
2
2. 把 3 放到根节点的右孩子，原来的子树作为 3 的左孩子
1
\
3
/
2
3. 把 3 放到根节点的右孩子的右孩子
1
\
2
\
3
以上就是根据[ 1 2 ]推出[ 1 2 3 ]的所有过程，可以写代码了。由于求当前的所有解只需要上一次的解，所有我们只需要两个list，pre保存上一次的所有解， cur计算当前的所有解。
以下是Java的题解代码实现。
public List<TreeNode> generateTrees(int n) {
List<TreeNode> pre = new ArrayList<TreeNode>();
if (n == 0) {
return pre;
}
pre.add(null);
//每次增加一个数字
for (int i = 1; i <= n; i++) {
List<TreeNode> cur = new ArrayList<TreeNode>();
//遍历之前的所有解
for (TreeNode root : pre) {
//插入到根节点
TreeNode insert = new TreeNode(i);
insert.left = root;
cur.add(insert);
//插入到右孩子，右孩子的右孩子...最多找 n 次孩子
for (int j = 0; j <= n; j++) {
TreeNode rootCopy = treeCopy(root); //复制当前的树
TreeNode right = root_copy; //找到要插入右孩子的位置
int k = 0;
//遍历 j 次找右孩子
for (; k < j; k++) {
if (right == null)
break;
right = right.right;
}
//到达 null 提前结束
if (right == null)
break;
//保存当前右孩子的位置的子树作为插入节点的左孩子
TreeNode rightTree = right.right;
insert = new TreeNode(i);
right.right = insert; //右孩子是插入的节点
insert.left = rightTree; //插入节点的左孩子更新为插入位置之前的子树
//加入结果中
cur.add(rootCopy);
}
}
pre = cur;
}
return pre;
}
private TreeNode treeCopy(TreeNode root) {
if (root == null) {
return root;
}
TreeNode newRoot = new TreeNode(root.val);
newRoot.left = treeCopy(root.left);
newRoot.right = treeCopy(root.right);
return newRoot;
}