Unique Binary Search Trees II
问题:
Given n, generate all structurally unique BST‘s (binary search trees) that store values 1...n.
思路:
dfs
我的代码:
public class Solution { public List<TreeNode> generateTrees(int n) { int[] num = new int[n]; for(int i = 0; i < n; i++) { num[i] = i + 1; } return findNode(num, 0, n); } public List<TreeNode> findNode(int[] num, int start, int end) { if(start == end) { List<TreeNode> list = new ArrayList<TreeNode>(); list.add(null); return list; } if(start + 1 == end) { List<TreeNode> list = new ArrayList<TreeNode>(); list.add(new TreeNode(num[start])); return list; } List<TreeNode> rst = new ArrayList<TreeNode>(); for(int i = start; i < end; i++) { List<TreeNode> left = findNode(num, start, i); List<TreeNode> right = findNode(num, i + 1, end); for(TreeNode l: left) { for(TreeNode r: right) { TreeNode root = new TreeNode(num[i]); root.left = l; root.right = r; rst.add(root); } } } return rst; } }
学习之处:
原文:http://www.cnblogs.com/sunshisonghit/p/4340239.html