Recursive method to verify whether a tree is a binary search tree (BST)

98. Verify binary search tree

Medium difficulty 1407

Give you the root node of a binary tree root , Determine whether it is an effective binary search tree .

It works The binary search tree is defined as follows ：

• The left subtree of the node contains only Less than Number of current nodes .
• The right subtree of the node contains only Greater than Number of current nodes .
• All left and right subtrees themselves must also be binary search trees .

Ideas

Verify whether a tree is BST Trees , We must be right about BST The definition of is very clear

• Left subtree All nodes The value of is less than the value of the current node
• Right subtree All nodes The value of is greater than the value of the current node

Therefore, we need to keep the maximum and minimum values from the root node to the current node during recursive traversal

Because the title explains that the value of each node can be taken int All numbers in the range , Then when we specify the minimum value, we can only specify long The minimum value of a type , It could go wrong

So when solving problems, you need to pay attention to the given data range , If the given data range is very large, don't consider the violence law ,99% It's going to be overtime

package cn.edu.xjtu.carlWay.tree.validateBinarySearchTree;

import cn.edu.xjtu.Util.TreeNode.TreeNode;

/** * 98.  Verify binary search tree  *  Give you the root node of a binary tree  root , Determine whether it is an effective binary search tree . * <p> *  It works   The binary search tree is defined as follows ： * <p> *  The left subtree of the node contains only   Less than   Number of current nodes . *  The right subtree of the node contains only   Greater than   Number of current nodes . *  All left and right subtrees themselves must also be binary search trees . * <p> * https://leetcode-cn.com/problems/validate-binary-search-tree/ */
public class Solution {
    
    public boolean isValidBST(TreeNode root) {
    
        return validBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    private boolean validBST(TreeNode root, long minValue, long maxValue) {
    
        if (root == null) {
    
            return true;
        }
        if (root.val < maxValue && root.val > minValue) {
    
            return validBST(root.left, minValue, root.val) && validBST(root.right, root.val, maxValue);
        }
        return false;
    }
}