• ㊗️
• 大家
• 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;
}
}