Different system and own execution results


  • 1
    A

    SOLVED

    public class Solution {
    
    boolean valid = true;
    
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        dfs(root);
        return valid;
    }
    
    int[] dfs(TreeNode v) {
        int[] left = null;
        int[] right = null;
        if (v.left != null) {
            left = dfs(v.left);
        }
        if (v.right != null) {
            right = dfs(v.right);
        }
        if (v.left != null) {
            if (v.right != null) {
                valid &= ((v.val > left[0]) && (v.val < right[1]));
                return new int[]{minTriple(v.val, left[0], right[0]), maxTriple(v.val, left[1], right[1])};
            }
            valid &= (v.val > left[1]);
            return new int[]{Math.min(v.val, left[0]), Math.max(v.val, left[1])};
        }
        if (v.right != null) {
            valid &= (v.val < right[0]);
            return new int[]{Math.min(v.val, right[0]), Math.max(v.val, right[1])};
        }
        return new int[]{v.val, v.val};
    }
    
    int maxTriple(int a, int b, int c){
        return (Math.max(a, Math.max(b, c)));
    }
    
    int minTriple(int a, int b, int c){
        return (Math.min(a, Math.min(b, c)));
    }
    

    Hello, everyone!

    I'm awfully sorry to ask one more dumb question, however, I stuck on one problem.
    I submitted the code above and got
    Input: {0,-1} Output: false Expected: true.

    I checked this case on my own machine and got true.

        public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        TreeNode l = new TreeNode(-1);
        root.left = l;
        System.out.println(new Solution().isValidBST(root));
    }
    

    Am I wrong in test case interpretation?
    The solution idea is simple: I return the min/max result from all subtrees and compare with the current vertex result, changing the valid variable if necessary.
    There are a bunch of other solutions, much more efficient, I see. But I want to know, why our results are not equal.

    Many thanks in advance,

    Kind regards.


  • 0
    A

    The same problem in one more problem, Path Sum II.
    It seems that the system doesn't update the previous attempt code.
    Why I think so?
    Had an
    Input: {1}, 0
    Output: [[1]]
    Expected: []
    Added special condition for '0' case, but had the same result => the code most not have been updated.


  • 0
    A

    Or this problem may occured due to global vars.


  • 0
    C

    yeah, I think you had better reset the global variables, which is clearly recommended by LeetCode. I guess they create just one instance of class, and call it several times.


  • 1
    A

    If anyone has this problem, you should initialize class members variables in the method, not in the definition place, i.e.:

    ..boolean valid;
    <your method definition>{
        valid = true;
        ...
    }
    

    instead of

    boolean valid = true;

  • 0
    A

    Thank you! I'll try some more attempts.


Log in to reply
 

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