天天看點

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);
    }
}


           

一:

98. 驗證二叉搜尋樹

二:

98. 驗證二叉搜尋樹

中序周遊

中序周遊,看是否是升序

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

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);
    }
}
           
98. 驗證二叉搜尋樹