98. 验证二叉搜索树

image.png

解题思路

主要思路：
利用中序遍历，如果为二叉搜索树，中序遍历是顺序的
double a= Double.NEGATIVE_INFINITY;//来记录中序遍历的前一个值，
//如果小于a，那么说明不是二叉搜索树，初始值为负无穷大
中序遍历时，为非递归，加一个stack

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
    double a= Double.NEGATIVE_INFINITY;//来记录中序遍历的前一个值
    Stack<TreeNode> s=new Stack<TreeNode>();
    while(root!=null||!s.isEmpty()){
        while(root!=null){
            s.push(root);
            root=root.left;
        }
     root=s.pop();
     if(root.val<=a) return false;
     a=root.val;//更新a的值，记录前一个元素的值
     root=root.right;
    }
    
     return true;
    }
}