98. 驗證二叉搜尋樹

遞歸

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

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


           

一：

二：

中序周遊

中序周遊，看是否是升序

一開始定義一個最小數，然後讓中序周遊的一次從前開始和他比，并把讓他依次等于中序中的數與後一個數比較，提高效率

class Solution {
    long pre = Long.MIN_VALUE;//A constant holding the minimum value a long can have, -263.   保持 long 類型的最小值的常量，該值為 -263。
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 通路左子樹
        if (!isValidBST(root.left)) {
            return false;
        }
        // 通路目前節點：如果目前節點小于等于中序周遊的前一個節點，說明不滿足BST，傳回 false；否則繼續周遊。
        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        // 通路右子樹
        return isValidBST(root.right);
    }
}