首页 > 代码库 > 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 3confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.OJ‘s Binary Tree Serialization:The serialization of a binary tree follows a level order traversal, where ‘#‘ signifies a path terminator where no node exists below.Here‘s an example: 1 / 2 3 / 4 5The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
难度：98。没有做出来的一道题，很难，参考了其他人的想法，发现基本上只有一个版本，在纸上按照它的步骤推了几步终于看懂了。分析如下：
第一次遇到这种让你construct a BST的问题，而且结果并不是建立一个ArrayList<ArrayList<Integer>>型的，而是建立一个ArrayList<TreeNode>型的，这我就不知道怎么搞了，看了别人的才发现原来只要把几种方案的root放在最终的结果ArrayList<TreeNode>里面就好了，每个root有自己的left & right，但是不用放在这个ArrayList里面，只要指定好就可以了。Note that current node needed to be created for each possible sub-tree setting.
以上是本问题的难点和不熟悉的地方，本题的思路参考了http://blog.csdn.net/linhuanmars/article/details/24761437
choose one number i from n as root, pass all the numbers less than i to recursive call to construct the current root‘s left sub-tree, pass all the numbers greater than i to the recursive call to construct the current root‘s right sub-tree. Take n=5 for example, when we choose root node = 3, then put 1,2 to recursive call to construct root node‘s left sub-tree, and put 4,5 to recursive call to contract root‘s right subtree.
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 ArrayList<TreeNode> generateTrees(int n) {12 return helper(1, n);13 }14 15 public ArrayList<TreeNode> helper(int left, int right){16 ArrayList<TreeNode> rs = new ArrayList<TreeNode>();17 if(left>right) rs.add(null);18 else if(left==right) rs.add(new TreeNode(left));19 else{20 for(int i=left; i<=right; i++){21 ArrayList<TreeNode> leftNodeSet = helper(left, i-1);22 ArrayList<TreeNode> rightNodeSet = helper(i+1, right);23 24 for(int j=0; j<leftNodeSet.size(); j++){25 for(int k=0; k<rightNodeSet.size(); k++){26 TreeNode curr = new TreeNode(i);27 curr.left = leftNodeSet.get(j);28 curr.right = rightNodeSet.get(k);29 rs.add(curr);30 }31 }32 }33 }34 return rs;35 }36 }
Leetcode: Unique Binary Search Trees II