I think OJ needs to be improved


  • 1
    M

    There could be multiple ways to solve. Why OJ only check one possibility?
    e.g., 2,1,3 tree, delete 2, I can have 1,null,3, && 3,1
    Both solutions are valid.
    I think OJ needs to check the result is BST and doesn't have key to delete.

    One simple solution scheme is just to substitute the target node with the left child's right most node. But it cannot pass OJ


  • 0

    @mmm713 I have just fixed this. I agree with you, now the OJ is able to check for multiple answers. Please try submitting again.


  • 0
    M

    My algorithm replaces the node A with the right child (B) and puts A's left child as the left child of the leftmost leaf in B (extra credit for understanding the explanation without looking at the example). However, as mentioned by mmm713, the OJ doesn't take it as a valid solution.

    E.g. of the said algorithm:

        2
     /      \
    0       33
     \     /  \
      1   25  40
             /  \
            34  45
             \
             36
    

    Removes 33

        2
     /      \
    0       40
     \     /  \
      1   34  45
         /  \
        25  36
    

    (Actual test case marked as failed)

    [2,0,33,null,1,25,40,null,null,11,31,34,45,10,18,29,32,null,36,43,46,4,null,12,24,26,30,null,null,35,39,42,44,null,48,3,9,null,14,22,null,null,27,null,null,null,null,38,null,41,null,null,null,47,49,null,null,5,null,13,15,21,23,null,28,37,null,null,null,null,null,null,null,null,8,null,null,null,17,19,null,null,null,null,null,null,null,7,null,16,null,null,20,6]
    33
    

  • 0

    @mmm713 @matiassm Why do you keep your code secret, so that we can't check whether it actually does what you think it does, and can't easily reproduce the alleged problem?


  • 0
    M

    @StefanPochmann not a secret (just didn't wanted to make a huge reply):

    public class Solution {
        public TreeNode deleteNode(TreeNode root, int key) {
            if (root == null) return root;
            if (root.val == key) return getReeplacement(root);
    
            TreeNode parent = findParent(root, key);
            if (parent != null) {
                if (parent.left != null && parent.left.val == key)
                    parent.left = getReeplacement(parent.left);
                else
                    parent.right = getReeplacement(parent.right);
            }
            return root;
        }
    
        private TreeNode getReeplacement(TreeNode node) {
            if (! (node.left != null && node.right != null)) return node.left != null? node.left : node.right;
    
            //Note: both children are not null
            TreeNode result = node.right;
            while (result.left != null) {
                result = result.left;
            }
            result.left = node.left;
            return node.right;
        }
    
        private TreeNode findParent(TreeNode node, int key) {
            TreeNode cur = node;
            TreeNode parent = null;
            while( cur != null && cur.val != key) {
                parent = cur;
                if (key < cur.val) cur = cur.left;
                else cur = cur.right;
            }
            return cur == null? null : parent;
        }
    }
    

  • 0
    M

    Also, it could be a bug in my code. However, if that was the case, maybe a way of improving the OJ is changing it error message from "I want this response" to: "the submitted solution is not valid. Here it's a valid solution: ..." (and maybe expose the input parsing logic to ease the task of debugging/trying alternate inputs.


  • 0

    @matiassm Hmm, I just submitted your solution and it got accepted. @1337c0d3r, did you change something?


  • 0
    M

    @StefanPochmann yes, now it's accepted. I don't know how the OJ works, but may be that the code run when failed was a previous version? (it didn't refreshed the code yet)


  • 0

    @StefanPochmann No, I did not change this question or its test cases for the past week. I've looked at @matiassm past submissions, and the code which got Wrong Answer is actually different from the code pasted here by one line:

    In the last line of getReeplacement method, the WA code is return result; instead of return node.right;.


  • 0
    M

    @1337c0d3r I submitted twice. First the code had that bug (the line that you mention) and then I corrected it and re-submitted. Maybe I re-submitted too fast and the code didn't upload correctly or something?


  • 0

    @matiassm Not sure what you meant. If you corrected it and re-submitted then get Accepted, then this is the intended behavior which I am seeing from your past submissions (You only submitted twice for this problem, the first WA and the second one get AC).


  • 0
    M

    @1337c0d3r that's odd, I could swear that I submitted the code I posted here (and that's why I thought there was a problem with the OJ). If you are not seeing that, maybe it was my mistake and I didn't submit that second time.


Log in to reply
 

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