When n is 0, why the OJ requires returning the list with a NULL pointer, not an empty list?


  • 4
    D

    I don't think it makes any sense to do so. When n is 0, we just cannot generate any trees, so the list should be empty.


  • 0
    Z

    I found there are many other problems with edge cases that do not make sense.
    A simple if(n==0){} would get around such problems as this issue does actually not bring much technical significance.


  • 0
    N

    It does seem odd when you think about it, but I actually found that including this edge case in my code with this result helped me simplify my solution. I ended up creating a helper function that generated trees from X-Y rather than 1-N, and I returned null when X > Y.


  • 0
    W

    If you think about how we define size 1 trees,
    then it's most natural and consistent to say that a tree with root==null has size 0.

    n=0 means we want the set of size 0 trees. It doesn't mean the set has size 0.
    The set is not empty, as it still contains an empty tree with root==null


  • 0
    A

    it's a bit odd, better to have more clarification.
    but i do find, at least in my code, returning an array with null makes my code simpler.

    /**
     * recursion(list<int> candidates)
     * pick any as root;
     * build left subtrees with candidates less than root, recursively;
     * build right subtrees wtih candidates greater than root, recursively.
     * use memo to improve performance.
     */
    private final Map<List<Integer>, List<TreeNode>> cache = 
        new HashMap<List<Integer>, List<TreeNode>>();
    public List<TreeNode> generateTrees(int n) {
        List<Integer> candidates = new ArrayList<Integer>();
        for (int i = 1; i <= n; i++)
            candidates.add(i);
        return generateTreesHelper(candidates);
    }
    
    private List<TreeNode> generateTreesHelper(List<Integer> candidates) {
        List<TreeNode> results = cache.get(candidates);
        if (results != null)
            return results;
        results = new ArrayList<TreeNode>();
        if (candidates.isEmpty()) {
            results.add(null); // just to make life easier :)
        } else {
            for (int i = 0; i < candidates.size(); i++) {
                int rootVal = candidates.get(i);
                List<TreeNode> lefts  = generateTreesHelper(candidates.subList(0, i));
                List<TreeNode> rights = generateTreesHelper(candidates.subList(i+1, candidates.size()));
                for (TreeNode left : lefts) {
                    for (TreeNode right : rights) {
                        TreeNode root = new TreeNode(rootVal);
                        root.left  = left;
                        root.right = right;
                        results.add(root);
                    }
                }
            }
        }
        cache.put(candidates, results);
        return results;
    }

  • 0
    J

    Adding a null to the result List make the code simple. Look at the following code which is the core of generating all the combinations of trees:

      for(TreeNode leftSubTree:leftSubTrees){
            for(TreeNode rightSubTree:rightSubTrees){
                TreeNode root=new TreeNode(rootValue);
                root.left=leftSubTree;
                root.right=rightSubTree;
                trees.add(root);
            }
       }
    

    without the null in the list, when the left or right lists are empty, the loop will exit right away, and your results will not be complete.


  • 0
    H

    Think about how we do the version 1 with DP approach. We think there is one and only one to create a tree with 0 nodes. So we should set null as the target node instead of empty


Log in to reply
 

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