Very Weird...What is wrong with my code


  • 0
    Y

    Here is my code:

    public class Solution {
    public ArrayList<TreeNode> generateTrees(int n) 
    {
       return helper(n,0);
    }
    public ArrayList<TreeNode> helper(int n,int k)
    {
        ArrayList<TreeNode> solution = new ArrayList<TreeNode>();
        if(n==0)
        {
            TreeNode cu = null;
            solution.add(cu);
            return solution;
        }
        else if(n==1)
        {
            TreeNode node = new TreeNode(n+k);
            solution.add(node);
            return solution;
        }
        else
        {
            for(int i=1;i<=n;i++)
            {
                ArrayList<TreeNode> a =  helper(i-1,k);
                ArrayList<TreeNode> a2 = helper(n-i,i+k);
                ArrayList<TreeNode> medium = new ArrayList<TreeNode>();
                for(int j=0;j<a.size();j++)
                {
                    TreeNode nd = new TreeNode(i+k);
                    nd.left = a.get(j);
                    medium.add(nd);
                }
                for(int j=0;j<medium.size();j++)
                {
                    for(int h=0;h<a2.size();h++)
                    {
                        TreeNode nd = medium.get(j);
                        nd.right = a2.get(h);
                        solution.add(nd);
                    }
                }
            }
            return solution;
        }
    }}
    

    The output is:
    Input: 3
    Output: [{1,#,3,2},{1,#,3,2},{2,1,3},{3,1,#,#,2},{3,2,#,1}]
    Expected: [{1,#,2,#,3},{1,#,3,2},{2,1,3},{3,1,#,#,2},{3,2,#,1}]
    Why {1,#,2,#,3} was replaced?


  • 0
    M

    Dang it Shangrila, I was working on that...

    TreeNode nd = medium.get(j);
                    nd.right = a2.get(h);
                    solution.add(nd);
                }
    

    a2.get(j) returns the same node you just added to solution, and then you overwrite its right child, causing the one already in solution to change. By adding it into solution again, you have a doubled answer. The reason it works on {3,1,#,2} and {3,2,#,1} is because the pair of answers occur in the left subtree, so each gets their own node to be a child of.

    If you merge the for loops, so you add left and right in the same section, you should get it to work.

    for(int j=0;j<a.size();j++){
    for(int h=0;h<a2.size();h++){
    TreeNode nd=new TreeNode(i+k);
    nd.left = a.get(j);
    nd.right = a2.get(h);
    solution.add(nd);
    }}


  • 0
    Y

    Thank you very much, I have got accepted after merging the for loops. But I am still confused. I think what you mean is "medium.get(j) return same node you just added to solution". But I am wandering why it happens, I new every Treenode nd, and then give it left, then add it to medium. How can medium.get(0) and medium.get(1) points to one node.


  • 0
    M

    medium.get(0) and medium.get(1) point to different trees. However, you call medium.get(j) multiple times in the h-based for loop for each value of j. If a2.size() == 2, then medium.get(0) will be called twice. If a2.size() == 3, then medium.get(0) will be called three times, and you would end up with 3 copies of the same tree.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.