题解 | 判断是不是二叉搜索树

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    //对叶子节点而言，没有左右节点值可以判断，所以设置一个最小值与根节点比较
    private int pre = Integer.MIN_VALUE;

    public boolean isValidBST (TreeNode root) {
        // 递归遍历 + 值判断
        // 1. 中序遍历，检查左子树中的值<根节点<右子树值
        // 2. 当搜索到叶子节点时返回
        
        //如果root为空树，也是一种二叉搜索树
        if(root == null){
            return true;
        }

        //1. 检查左子树是否为二叉搜索树
        if(!isValidBST(root.left)){
            return false;
        }

        //2. 对当前根节点进行判断
        if(root.val < pre){
            return false;
        }
        pre = root.val;

        //3. 检查右子树是否为二叉搜索树
         if(!isValidBST(root.right)){
            return false;
        }
        

        return true;
    }

}

和二叉树有关类型的问题，通常都可以用归并思想考虑。例如此题需要判断一颗二叉树是否为二叉搜索树，那么就需要从二叉搜索树的特点思考。

1. 二叉搜索树的特点：该树的左子树中的值 < 根节点.val < 右子树.val
2. 根据以上特点可以联想到：中序遍历。

解题思路：按照中序遍历去检查 1.左子树是否为二叉搜索树？2. root.val 是否大于 prev_root.val？3. 右子树是否为二叉搜索树？并将这三个问题用归并的思想循环调用方法进行判断。

因此这里需要设置一个全局变量值prev，始终记录前一节点的值，并与当下值判断是否满足升序要求。并在判断完成后更新prev值。