/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    static class ReturnData {
        public boolean isBST;
        public int max;
        public int min;
        public ReturnData(boolean is, int mi, int ma) {
            isBST = is;
            min = mi;
            max = ma;
        }
    }

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        ReturnData res = check(root);
        if (res == null) {
            return true;
        }
        return res.isBST;

    }

    private ReturnData check(TreeNode node) {
        if (node == null) {
            return null;
        }

        int min = node.val;
        int max = node.val;
        ReturnData left = check(node.left);
        ReturnData right = check(node.right);

        if (left != null) {
            min = Math.min(min, left.min);
            max = Math.max(max, left.max);
        }

        if (right != null) {
            min = Math.min(min, right.min);
            max = Math.max(max, right.max);
        }
        boolean isBST = true;
        if (left != null && (!left.isBST || left.min >= node.val)) {
            isBST = false;
        }
        if (right != null && (!right.isBST || right.min <= node.val)) {
            isBST = false;
        }
        return new ReturnData(isBST, min, max);
    }
}

I want to ask a LeetCode question, Question 98. The question wants me to write an algorithm to check whether the given tree is a valid binary tree, so I wrote like this:

1. I create a constructor to initialize the return type, which contains the current node's value, max, and min value of its subtree.
2. I want to use recursion to check the validation.

But it doesn't work, I also check the solution but I still don't know why this way didn't work.

Hope someone could give me a hint, thanks.

CodePudding user response：

The problem is in this condition:

left.min >= node.val

You'll want to see whether the maximum in the left tree exceeds the current node's value, so:

left.max >= node.val