98. Validate Binary Search Tree

DFS

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }

    private boolean isValidBST(TreeNode node, Integer minValue, Integer maxValue) {
        if (node == null) {
            return true;
        }
        if (minValue != null && node.val <= minValue) {
            return false;
        }
        if (maxValue != null && node.val >= maxValue) {
            return false;
        }

        return isValidBST(node.left, minValue, node.val) && isValidBST(node.right, node.val, maxValue);
    }
}

需要注意的是题目要求节点的左子树中的所有节点值小于当前节点，右子树中的所有节点值大于当前节点，而不仅是左子节点小于当前节点，右子节点大于当前节点。

DFS

class Solution {
    private static class State {
        private Integer preValue;
    }
    
    public boolean isValidBST(TreeNode root) {
        // left -> root -> right

        State state = new State();
        return dfs(root, state);
    }

    private boolean dfs(TreeNode node, State state) {
        if (node == null) {
            return true;
        }

        if (!dfs(node.left, state)) {
            return false;
        }

        if (state.preValue != null && node.val <= state.preValue) {
            return false;
        }
        state.preValue = node.val;

        return dfs(node.right, state);
    }
}

Iterate

class Solution {
    public boolean isValidBST(TreeNode root) {
        // left -> root -> right

        TreeNode pre = null;

        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            // now: root is null
            TreeNode node = stack.pop();
            if (pre != null && node.val <= pre.val) {
                return false;
            }
            pre = node;

            root = node.right;
        }

        return true;
    }
}

我们利用二叉搜索树的中序遍历为递增的特性，采用中序遍历来检查一个树是否是二叉搜索树。

Reference

98. Validate Binary Search Tree