题目描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

样例

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

算法1

(dfs) $O(n)$

* 中序遍历序列递增，记录每个节点的前一个节点，如果有逆序对，则不是二叉搜索树

Java代码

class Solution {
    TreeNode last = null;
    boolean flag = true;
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        dfs(root);
        return flag;
    }

    void dfs(TreeNode root){
        if(root == null) return;
        if(root.left != null) dfs(root.left);
        if(last != null && last.val >= root.val){
            flag = false;
            return;
        }
        last = root;
        if(root.right != null) dfs(root.right);
    }
}