https://oj.leetcode.com/problems/validate-binary-search-tree/
1.中序遍历是否有序
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
private int a=-(1<<31);
public boolean isValidBST(TreeNode root) {
return middle(root);
}
public boolean middle(TreeNode root)
{
if(root==null) return true;
if(!middle(root.left)) return false;
if(root.val<=a)
{
return false;
}
a=root.val;
return middle(root.right);
}
}
2.记住每个节点的范围 开始时候（min,max）设为int最大，最小，然后在左子树上范围为（min, root.val） 判断节点是否在范围；
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public boolean isValidBST(TreeNode root) {
int min=-(1<<31);
int max=1<<31-1;
return isValid(root,min,max);
}
public boolean isValid(TreeNode root,int min,int max)
{
if(root==null) return true;
if(root.val>min&&root.val<max)
{
return isValid(root.left,min,root.val)&&isValid(root.right,root.val,max);
}
return false;
}
}