(Invalid) Bug: A (in)valid O(n) solution is not accepted by the judge


  • 0
    R

    [Update] The following is invalid because I didn't notice that the three has to be "height balanced" which means that for each node the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1. Thanks Stefan for pointing this out.

    This is what I get from the judge when submitting one of the solutions. It is a valid solution, but the judge doesn't accept it. Is there a way to file a bug report?

    Input:
    [-1,0,1,2]
    Output:
    [2,0,null,-1,1]
    Expected:
    [1,0,2,-1]
    

    The O(n) java solution that causes the bug:

    public class Solution {
        private static class State {
            ListNode head;
            State(ListNode head) {
                this.head = head;
            }
        }
        public TreeNode sortedListToBST(ListNode head) {
            return sortedListToBST(Integer.MAX_VALUE, new State(head));
        }
        private TreeNode sortedListToBST(int limit, State state) {
            if (limit == 0 || state.head == null) return null;
            int depth = 1;
            TreeNode root = new TreeNode(state.head.val);
            state.head = state.head.next;
            limit--;
            while (state.head != null && limit > 0) {
                TreeNode newRoot = new TreeNode(state.head.val);
                state.head = state.head.next;
                newRoot.left = root;
                root = newRoot;
                limit--;
                int rightLimit = (int)Math.pow(2,depth) - 1;
                root.right = sortedListToBST(rightLimit, state);
                limit -= rightLimit;
                depth++;
            }
            return root;
        }
    }

  • 0

    [2,0,null,-1,1] is not acceptable. The root's left subtree is two levels higher than its right subtree.


  • 0
    R

    Thanks for pointing this out. I've updated the post to say that this is an invalid bug.


Log in to reply
 

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