首页 > 代码库 > Leetcode-Unique Binary Search Trees II
Leetcode-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
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
Have you met this question in a real interview?
Solution:
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 List<TreeNode> list = generateTreesRecur(n,1,n);13 return list;14 15 }16 17 public List<TreeNode> generateTreesRecur(int len, int s, int e){18 List<TreeNode> treeList = new ArrayList<TreeNode>();19 if (len==0){20 treeList.add(null);21 return treeList;22 }23 24 if (len==1){25 TreeNode newNode = new TreeNode(s);26 treeList.add(newNode);27 return treeList;28 }29 30 for (int i=s;i<=e;i++){31 int leftLen = i-s;32 int rightLen = e-i;33 List<TreeNode> leftList = generateTreesRecur(leftLen,s,i-1);34 List<TreeNode> rightList = generateTreesRecur(rightLen,i+1,e);35 for (int j=0;j<leftList.size();j++)36 for (int k=0;k<rightList.size();k++){37 TreeNode root = new TreeNode(i);38 root.left = leftList.get(j);39 root.right = rightList.get(k);40 treeList.add(root);41 }42 43 }44 45 return treeList;46 47 }48 }
Leetcode-Unique Binary Search Trees II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。