Force deduction brush question - 98 Validate binary search tree

Daily clock in algorithm problem

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

A valid binary search tree is defined as follows ：

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

 

  The class definition of the following binary tree is given

/**
 * 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;
 *     }
 * }
 */

Their thinking ：

First, let's analyze the problem , The subject is very simple , It is to judge whether a given binary tree is a binary search tree .

Binary search tree ：

        1. For the binary tree, the maximum value of the left subtree of any node is less than the value of the node

        2. For any node of the binary tree, the minimum value of the right subtree is greater than the value of the node

        3. The left and right subtrees of any node of the binary tree are binary search trees

Set upper and lower bounds ：

         Every time I recurse to the left , Keep the original minimum value unchanged , Set the value of the current intermediate node to the upper bound

         Every time I recurse to the right , Keep the original maximum value unchanged , Set the value of the current intermediate node to the lower bound

Set recursive exit ：

        Obviously , If the value of the current node does not meet the upper and lower bounds , Then the subtree is not a binary search tree , The root node is not satisfied .

    public boolean isValidBST(TreeNode root){
        return isValidBST(root,10000000000L,-10000000000L);
    }
    public boolean isValidBST(TreeNode root,long top,long low) {
        if (root.val <= low || root.val >= top){
            return false;
        }
        
        boolean left = false;
        boolean right = false;
        if(root.left != null){
            left = isValidBST(root.left,root.val,low);
        }else {
            left = true;
        }
        if (root.right != null){
            right = isValidBST(root.right,top, root.val);
        }else {
            right = true;
        }
        
        if (left && right){
            return true;
        }else {
            return false;
        }
    }

Pruning optimization ：

        The code verifies that the binary sort tree must pass through all nodes , If the binary tree is a sort binary tree , Then there is no doubt that all nodes will be verified , But if the tree is not a sorted binary tree , Other recursive paths will continue to be verified , So you can set a global variable outside the method boolean flag = true; Indicates that there are no nodes that are not satisfied , When dissatisfaction occurs, it is set to false, At this time, the initial judgment of the entry method flag, If false Cancel code running directly .

    boolean flag = true;
    public boolean isValidBST(TreeNode root){
        return isValidBST(root,10000000000L,-10000000000L);
    }
    public boolean isValidBST(TreeNode root,long top,long low) {
        if(!flag){
            return false;
        }
        if (root.val <= low || root.val >= top){
            return false;
        }
        
        boolean left = false;
        boolean right = false;
        if(root.left != null){
            left = isValidBST(root.left,root.val,low);
        }else {
            left = true;
        }
        if (root.right != null){
            right = isValidBST(root.right,top, root.val);
        }else {
            right = true;
        }
        
        if (left && right){
            return true;
        }else {
            return false;
        }
    }