Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.
1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
public class Solution { public ArrayList<TreeNode> generateTrees(int n) { return dfs(0,n-1); } public ArrayList<TreeNode> dfs(int begin, int end){ ArrayList<TreeNode> result = new ArrayList<TreeNode>(); if(begin > end){ result.add(null); return result; } for(int k = begin;k <= end ;k++){ ArrayList<TreeNode> left = dfs(begin,k-1); ArrayList<TreeNode> right = dfs(k+1,end); for(int i = 0 ; i < left.size();i++){ for(int j = 0; j < right.size(); j++){ TreeNode root = new TreeNode(k+1); root.left = left.get(i); root.right = right.get(j); result.add(root); } } } return result; } }