98. Validate Binary Search Tree - Medium

前往題目

搬運一下之前寫過的

想法

• 要檢查數值，還要檢查是否是BST
• 紀錄擁有子樹的node的數值，然後檢查左邊，比較數值，有錯就直接結束；右邊也是一樣
• 檢查是否是BST得用height，左右子樹的高度差不能超過1

思路

1. Recursion檢查每個node是否小於等於最小值，或是否大於等於最大值，如果有就是false

Code

嘗試寫了，但邏輯有誤，沒有考慮到左子樹有可能會比右子樹的某一項還大，而且看起來很冗餘…

▶

WA

// WA
class Solution {
    public boolean isValidBST(TreeNode root) {
        return valid(root);
    }

    private boolean valid (TreeNode node) {
        if (node == null) return true;

        boolean left = true, right = true;

        if (node.left != null) {
            left = valid(node.left);
            if (node.left.val >= node.val) return false;
        }

        if (node.right != null) {
            right = valid(node.right);
            if (node.right.val <= node.val) return false;
        }

        return true;
    }
}

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

    private boolean check(TreeNode node, long min, long max) {
        // Go back when no more child
        if (node == null) return true;

        // Check each node
        if (node.val <= min || node.val >= max) return false;

        return check(node.left, min, node.val) && check(node.right, node.val, max);
    }
}