求大牛帮忙找Bug, LeetCode Unique Binary Search Trees II

就是那道要输出所有不同的BST的题： 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我的解法如下：

public class Solution {

public List<TreeNode> generateTrees(int n) {

ArrayList<TreeNode> result = new ArrayList<TreeNode>();

if(n==0){

result.add(null);

return result;

}

if(n==1){

TreeNode root = new TreeNode(1);

result.add(root);

return result;

}

for(int i=1;i<=n;i++){

for(TreeNode node:generateTrees(i-1)){

for(TreeNode rightNode:generateTrees(n-i)){

TreeNode root = new TreeNode(i);

root.left = node;

addVal(rightNode,i);

root.right = rightNode;

result.add(root);

}

}

}

return result;

}

public void addVal(TreeNode root, int i){

if(root==null)

return;

root.val += i;

if(root.left!=null)

addVal(root.left,i);

if(root.right!=null)

addVal(root.right,i);

}

}

但是到input n=5的时候就wrong answer了.....盯着屏幕看了好久还是看不出哪儿错了啊~！！求助哇~！！！

而且很奇怪的是在n=5的时候输出的很多组里也只有以下两组不一样：

Input:	5
Output:	{1,#,3,3,4,#,#,#,5},{1,#,3,3,5,#,#,4}
Expected:	{1,#,3,2,4,#,#,#,5},{1,#,3,2,5,#,#,4}

知道有一种用start, end 两个index做recursion的方法，但我不想用啊因为感觉我这个也没错啊，不知道bug在哪儿啊跪求大牛指点~！！！