98. Validate Binary Search Tree

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.

The right subtree of a node contains only nodes with keys greater than the node’s key.

Both the left and right subtrees must also be binary search trees.

Example 1:

Input:
    2
   / \
  1   3
Output: true

Example 2:

    5
   / \
  1   4
     / \
    3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
             is 5 but its right child's value is 4.

Code

class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        return helper(root.left, Long.MIN_VALUE, root.val) &&
        helper(root.right, root.val, Long.MAX_VALUE);
    }

    private boolean helper(TreeNode root, long min, long max){
        if(root == null) return true;
        if(root.val <= min || root.val >= max) return false;

        return helper(root.left, min, root.val) &&
        helper(root.right, root.val, max);
    }
}

class Solution {
    Integer pre = null;
    boolean res = true;
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;
        helper(root);
        return res;
    }

    private void helper(TreeNode root){
        if(root == null) return;

        helper(root.left);

        if(pre != null && root.val <= pre){
            res = false;
        }
        pre = root.val;

        helper(root.right);
    }
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root == null) return true;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        Integer pre = null;

        while(!stack.isEmpty() || curr != null){
            while(curr != null){
                stack.push(curr);
                curr = curr.left;
            }

            curr = stack.pop();
            if(pre != null && curr.val <= pre){
                return false;
            }

            pre = curr.val;
            curr = curr.right;
        }

        return true;
    }
}