Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- // O(n^2) O(n^2)
- public List<TreeNode> generateTrees(int n) {
- if (n == 0) return new ArrayList<TreeNode>();
- return genTree(1, n);
- }
- private List<TreeNode> genTree(int start, int end) {
- List<TreeNode> list = new ArrayList<>();
- if ( start > end ) {
- list.add(null);
- return list;
- }
- // this part can be ignored
- if ( start == end ) {
- list.add(new TreeNode(start));
- return list;
- }
- List<TreeNode> left, right;
- for (int i=start; i<=end; i++) {
- left = genTree(start, i-1);
- right = genTree(i+1, end);
- for (TreeNode lnode : left) {
- for (TreeNode rnode : right) {
- TreeNode root = new TreeNode(i);
- root.left = lnode;
- root.right = rnode;
- list.add(root);
- }
- }
- }
- return list;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement