登录
  • #刷题
  • #leetcode

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

tbu
1400
3
就是那道要输出所有不同的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在哪儿啊跪求大牛指点~!!!
3条回复
热度排序

发表回复