Unique Binary Search Trees II
给一个数, 返回所有可能的BST. 找到所有的卡塔兰数组合.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public ArrayList<TreeNode> generateTrees(int n) { return generate(1,n); } public ArrayList<TreeNode> generate (int start, int end) { ArrayList<TreeNode> res = new ArrayList<TreeNode>(); if(start > end){ res.add(null); return res; } for(int i = start; i <= end; i++) { ArrayList<TreeNode> left = generate(start, i - 1); ArrayList<TreeNode> right = generate(i+1, end); for(TreeNode l : left){ for(TreeNode r : right) { TreeNode root = new TreeNode(i); root.left = l; root.right = r; res.add(root); } } } return res; } } |