Validate Binary Search Tree (Java)

LeetCode

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.

	/*
	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.
	*/
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	public class ValidateBinarySearchTree {
	public boolean isValidBST(TreeNode root) {
	if (root==null){
	return true;
	}
	return check(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
	}
	private boolean check(TreeNode root, int left, int right){
	if (root==null){
	return true;
	}
	if (root.val<=left ||root.val>=right){
	return false;
	}
	return check(root.left, left, root.val) && check(root.right, root.val, right);
	}
	}
	public class ValidateBinarySearchTree {
	public boolean isValidBST(TreeNode root) {
	if (root==null){
	return true;
	}
	int[] pre={Integer.MIN_VALUE};
	return check(root, pre);
	}
	private boolean check(TreeNode root, int[] pre){
	if (root==null){
	return true;
	}
	if (!check(root.left, pre)){
	return false;
	}
	if (pre[0]>=root.val){
	return false;
	}
	else{
	pre[0]=root.val;
	}
	if (!check(root.right, pre)){
	return false;
	}
	return true;
	}
	}

view raw ValidateBinarySearchTree .java hosted with ❤ by GitHub