Runtime Error: for input {0,1}


  • 0
    N

    Not sure why my following solution has the Runtime Error: Last executed input: {0,1}

    public void recoverTree(TreeNode root) {
        if(root == null) return;
        ArrayList<TreeNode> swapedNodes = new ArrayList<TreeNode>();
        checkNode(root, swapedNodes);
        //assertEquals("doesn't have two nodes swaped", 2, swapNodes.size());
        swapNodes(swapedNodes.get(0), swapedNodes.get(1));
    }
    
    //helper function to check if the node is a swaped node or not
    //the swaped node should not fall into: node>node.left&&node<node.right
    public void checkNode(TreeNode root, ArrayList<TreeNode> result) {
       if (root == null) {
           return;
       }
       int leftVal = Integer.MIN_VALUE;
       int rightVal = Integer.MAX_VALUE;
       if (root.left != null) {
           leftVal = root.left.val;
       }
       
       if (root.right != null) {
           rightVal = root.right.val;
       }
       if (!((root.val <= rightVal) && (root.val >= leftVal))) {
           result.add(root);
       }
       checkNode(root.left, result);
       checkNode(root.right, result);
    }
    
    public void swapNodes(TreeNode a, TreeNode b) {
        int tmp = a.val;
        a.val=b.val;
        b.val=tmp;
    }

  • -1
    M

    As you know, your algorithm goes through the tree and finds the nodes that are out of place by looking at its children. However, it also assumes that the children and leaves are in the right place.

    The current tree has the root notice that its left child is greater, so the root is added, correctly. The next step, however, looks at the left child. Its children are null, so it compares against MAX and MIN, both of which follow correctly. MIN is definitely less than val, and MAX is more. Therefore, the leaf will not be added to the list. You then return and try to swap index 1 of a length 1 array. This creates the error you are seeing.

    On the other hand, assume that the root had a right child, less than the root. In that case, the root was in the correct place, while the children needed to be switched. However, the current algorithm will note that the children are not in the proper order and add the root to the list to be switched. Assuming you had fixed the problem from the previous paragraph, you would notice the leaves were also in the wrong position. They get added, and then the left child and root are switched, ending the program, but giving you the wrong answer.


Log in to reply
 

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