题意：

题解：

中序遍历 + 一个最小值

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    long pre=Long.MIN_VALUE;
    boolean flag=true;
    //
    public boolean isValidBST(TreeNode root) {
        
        dfs(root);
        
        return flag;
    }
    private void dfs(TreeNode root){
        if(root == null) return;
        if(root.left!=null){
            dfs(root.left);
        }
        
        if(pre >=root.val){
            flag=false;
        }else{
            pre=root.val;
        }
        if(root.right!=null){
            dfs(root.right);
        }
    }
}

99恢复搜索二叉树

题解：

在中序遍历中 从小到大排列

如果 出现两个点 a(i)>a(i+1) 与 a(j)>a(j+1);

如果出现一个点 a(i)>a(i+1) 那么只需交换 i 和 i+1 即可

而i是第一次出现的  j是第二次出现

可以构造两个空结点 保存着两个值

再交换

题解：

class Solution {
    TreeNode pre,t1,t2;
    public void recoverTree(TreeNode root) {
        dfs(root);
        swap(t1,t2);
        return;
    }
    private void swap(TreeNode t1,TreeNode t2){
        int tem;
        tem=t1.val;
        t1.val=t2.val;
        t2.val=tem;
    }
    private void dfs(TreeNode root){
        if(root == null) return;
        dfs(root.left);
        if(pre!=null && pre.val >= root.val){
            if(t1==null) t1=pre;
            t2=root;
            
        }
        pre = root;
        dfs(root.right);
    }
}

当然这题可以继续优化 使得空间复杂度为O(1)