Leetcode problem solving -- 98 Validate binary search tree

Recursive version

public boolean isValidBST(TreeNode root) {
    
    return range(root,Integer.MIN_VALUE-1L,Integer.MAX_VALUE+1L);
}

public boolean range(TreeNode node,long min,long max){
    
    if (node==null) return true;
    if (node.val<=min||node.val>=max)  return false;
    return range(node.left,min,node.val)&&range(node.right,node.val,max);
}

Wrong thinking ：

Before saying the right way of thinking , Let me first talk about the pit I stepped on , I was thinking about recursion , Then judge whether the value of the left node is greater than or equal to the root node or the value of the right node is less than or equal to the root node , Just go back to false, But in fact, this is not possible , Please look at the chart below.

         7
       /   \
      2     5
     / \
    1   9

According to the above idea, the result is true, This is because the upper limit of the left subtree is ignored , And the right subtree has the error caused by the lower limit

The right way of thinking ：

Use the upper and lower limits to judge

• Because the root node has no upper and lower limits , Therefore, the maximum and minimum values that can be stored by the variable type are used as the upper and lower limits
• If the node is null Go straight back to true
• If the node is not null, And the node value is not within the range specified by the upper and lower limits ,return false
• Continue to judge subtree , But should pay attention to , The upper limit of the left subtree is the value of the current subtree , The lower limit of the right subtree is the value of the current subtree

Iteration version

public boolean isValidBST(TreeNode root) {
    
    Stack<TreeNode> stack = new Stack<>();
    TreeNode node = root;
    long prev = Integer.MIN_VALUE-1L;
    while (!stack.isEmpty()||node!=null){
    
        while (node!=null){
    
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        if (node.val<=prev) return false;
        prev = node.val;
        node = node.right;
    }
    return true;
}

Ideas ：
BSTree In the middle order traversal of , The value of the previous node to be traversed must be less than the value of the next node to be traversed , Therefore, a node that stores the value of the previous traversed node is added prev Variables for comparison
This scheme is based on the understanding of the iterative method of middle order traversal , If a little partner doesn't know , And I want to know more about the explanation idea of middle order traversal iteration , Sure Click here to jump