题目
https://leetcode.com/problems/validate-binary-search-tree
判断所给二叉树是否是二叉搜索树
二叉搜索树：其值left<root<right
*[2,2,2]这种相等的情况也不是搜索树
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid 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: root = [2,1,3]
Output: true
Example 2:
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
思路
参考：https://www.bilibili.com/video/BV1VK411N7vm
首先最直观的方法，从左到右值越来越大
想到使用中序遍历（左中右），将所有元素提取出来成list
如果是搜索树，则list里的元素值依次递增
再对list遍历，如果list[i+1]<list[i] 则返回false结束
遍历完成，返回true
法二
上面的思路遍历了两次，时间空间复杂度↑ 优化，在遍历时就开始判断
以root对半分
root左取值范围【负无穷，root值】
root右取值返回【root值，正无穷】
*注意因为这里int类型，题目说int_min/max都能取到，所有我们tmp出的初始正负无穷要用long，更大
代码
法一
https://www.cnblogs.com/inku/p/15163602.html
class Solution {
List<Integer> list=new ArrayList<>();
public void inorder(TreeNode root){
if (root==null)
return;
inorder(root.left);
list.add(root.val);
inorder(root.right);
}
public boolean isValidBST(TreeNode root) {
if(root==null)
return true;
inorder(root);
int min=list.get(0);
for(int i=1;i<list.size();i++){
if (min>=list.get(i)){
return false; //严格小于，等于也是false
}
else{
min=list.get(i);
}
}
return true;
}
}
法二
class Solution {
public boolean isValidBST(TreeNode root) {
return fun(root,Long.MIN_VALUE,Long.MAX_VALUE);//初始化最大最小值
}
public boolean fun(TreeNode root,Long min,Long max){
if (root==null)
return true;
boolean left=fun(root.left,min,(long)root.val);//root左边，最大不超过root，值越来越小
//反之，返回false
if(root.val<=min||root.val>=max)
return false;
boolean right=fun(root.right,(long)root.val,max);//root右边，最小不小于root，值越来越大
return left&&right;//二者中一个false，就为false
}
}