Return 0 / 1 ( 0 for false, 1 for true ) for this problem
Method:
Check if root's value is in range, then recursively on it's children
Solution:
Time: O(n) Space: O(h)
/**
* Definition for binary tree
* class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) {
* val = x;
* left=null;
* right=null;
* }
* }
*/
public class Solution {
// 3
// 2 4
// 1 3
public int isValidBST(TreeNode A) {
return isValidBST(A, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private int isValidBST(TreeNode A, int min, int max) {
if (A == null) return 1;
if (A.val <= min || A.val >= max) {
return 0;
}
int left = isValidBST(A.left, min, A.val);
int right = isValidBST(A.right, A.val, max);
return Math.min(left, right);
}
}
class Solution {
public boolean isValidBST(TreeNode root) {
long min = Long.MIN_VALUE;
long max = Long.MAX_VALUE;
return isValid(root, min, max);
}
private boolean isValid(TreeNode root, long min, long max) {
if (root == null) return true;
long val = (long) root.val;
if (val <= min || val >= max) return false;
return isValid(root.left, min, val) && isValid(root.right, val, max);
}
}