首页 > 代码库 > [leetcode]Unique Binary Search Trees II
[leetcode]Unique Binary Search Trees II
Unique Binary Search Trees II
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
算法思路：
分治法：求出左子树的list和右子树的list，然后循环两个子树，分别插入root的左右子树。
代码如下：
1 /** 2 * Definition for binary tree 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; left = null; right = null; } 8 * } 9 */10 public class Solution { 11 public List<TreeNode> generateTrees(int n) {12 return buildTree(1,n);13 }14 private List<TreeNode> buildTree(int begin,int end){15 List<TreeNode> res = new ArrayList<TreeNode>();16 if(begin > end){17 res.add(null);18 return res;19 }20 List<TreeNode> left = new ArrayList<TreeNode>();21 List<TreeNode> right = new ArrayList<TreeNode>();22 for(int i = begin; i <= end; i++){23 left = buildTree(begin, i - 1);24 right = buildTree(i + 1, end);25 for(int j = 0; j < left.size(); j++){26 for(int k = 0; k < right.size(); k++){27 TreeNode node = new TreeNode(i);28 node.left = left.get(j);29 node.right = right.get(k);30 res.add(node);31 }32 }33 }34 return res;35 }36 }
参考：
http://www.cnblogs.com/cheapcrook/archive/2013/01/29/2880903.html
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。