Different system and own execution results

Question

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.

Comments

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.

---

Or this problem may occured due to global vars.

---

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.

---

Thank you! I'll try some more attempts.

Answer 1

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;