題目
連結:https://leetcode-cn.com/problems/unique-binary-search-trees-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
分治
思路:
由于是二叉搜尋樹是以它的特點是中間節點大于左子樹所有節點,小于右子樹所有節點。
一個
[1~n]
的序列可以看作二叉搜尋樹的中序周遊,序列中的數字
i
可以作為中間節點,而
[1~i-1]
為左子樹的節點,
[i+1~n]
為右子樹的節點,是以可以通過遞歸得到左子樹的集合與右子樹的集合,然後通過周遊兩個集合将左子樹與右子樹互相組合即可得到所有二叉搜尋樹。
/**
* 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 LinkedList<>();
return generateSubTrees(1, n);
}
private List<TreeNode> generateSubTrees(int start, int end) {
List<TreeNode> allTrees = new LinkedList<>();
if (start > end) {
allTrees.add(null);
return allTrees;
}
for (int i = start; i <= end; i++) {
List<TreeNode> leftTrees = generateSubTrees(start, i - 1);
List<TreeNode> rightTrees = generateSubTrees(i+1, end);
for (TreeNode l : leftTrees) {
for (TreeNode r : rightTrees) {
TreeNode cur = new TreeNode(i);
cur.left = l;
cur.right = r;
allTrees.add(cur);
}
}
}
return allTrees;
}
}