LeetCode 二叉搜索树系列 ～ 验证二叉搜索树

携手创作，共同成长！这是我参与「掘金日新计划 · 8 月更文挑战」的第5天，点击查看活动详情

二叉搜索树的定义

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

题目

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

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

示例

输入： root = [2,1,3]
输出： true

输入： root = [5,1,4,null,null,3,6]
输出： false
解释： 根节点的值是 5 ，但是右子节点的值是 4 。

提示

• 树中节点数目范围在[1, 10^4] 内
• -2^31 <= Node.val <= 2^31 - 1

中序遍历

/** * 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 {
    // 用来保存前一节点元素值
    private long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        // 边界判断
        if(null == root){
            return true;
        }

        // 先递归左节点，找到最左边的节点。后序的节点再进行比较
        if(!isValidBST(root.left) || root.val <= pre){
            return false;
        }
        
        // 更新上一节点元素值
        pre = root.val;

        // 递归比较右边节点
        return isValidBST(root.right);
    }
}