LeetCode 98. 验证二叉搜索树

1、题目

image.png

2、分析

思路一：
可以使用BTS的中序遍历是升序排列的特性来判断

思路二：
利用BTS的定义：root 的整个左子树都要小于 root.val，整个右子树都要大于 root.val
把当前节点的root的限制，递归一层一层传下去。判断。

3、代码

思路一代码：利用中序遍历

/**
 * 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 {
    int val = Integer.MIN_VALUE;
    int flag = 0;
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        if(!isValidBST(root.left)){
            return false;
        }
        if(root.val <= val && flag != 0) return false;
        val = root.val;
        flag = 1;
        if(!isValidBST(root.right)){
            return false;
        }
        return true;
    }
}

思路二：利用迭代的思想

/**
 * 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 {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }

    private boolean isValidBST(TreeNode root, TreeNode min, TreeNode max){
        if(root == null) return true;
        if(min != null && root.val <= min.val) return false;
        if(max != null && root.val >= max.val) return false;
       //左子树的最大值是 root.val，右子树的最小值是 root.val
        return isValidBST(root.left, min, root) && isValidBST(root.right, root, max);
    }
}