一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 856|回复: 3
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
tbu 发表于 2014-9-8 13:27:12 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
就是那道要输出所有不同的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在哪儿啊跪求大牛指点~!!!


 楼主| tbu 发表于 2014-9-9 11:41:34 | 显示全部楼层
怎么木有人回
顶上来
回复 支持 反对

使用道具 举报

li24yang75 发表于 2014-9-25 10:19:31 | 显示全部楼层
你这解法,我也是看的醉了!!!我也没发现怎么会有个节点多加了一次。。。。
回复 支持 反对

使用道具 举报

nano 发表于 2014-10-8 23:09:04 | 显示全部楼层
非牛人,本人也不太懂java,但是近期内被bake了太多的java的问题,试着回答一下,以下纯属猜想,没有上调试器验证

楼主的问题出在n=5时左树的值多加了,我个人认为这是java pass by reference 所致
出问题的树是n=5, i=1,(记为第一层) 然后递归调用生成rightnode时n=4,i=2, (记为第二层)然后递归调用生成右树n=2,i=1(记为第三层)

我们先考虑第三层的问题,可以有1 #2 和 2 1 两种情况,然后这两棵树的根节点返回第二层。
第二层的情况,左子树只有一种可能,就是1,然后你的node作为1的引用,和右子树1#2搭配,生成一棵新树 2 1 3 # # # 4,压进result,同样一个node,指向同样的内存地址,和右子树21搭配,生成一课新树 214##3,压进result,这个就是典型的应该deep copy但可能实际SHALLOW COPY了
第一层的情况现在就很明了了,那个左树被加了两次
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 02:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表