博客

​
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private boolean ret = true;
    public boolean isValidBST(TreeNode root) {
        if(root==null){
            return true;
        }
        long maxnum = 111111111111111111L;
        long minnum = -1111111111111111111L;
        this.dfs(root,maxnum,minnum);
        return this.ret;
    }
    public void dfs(TreeNode root,long maxnum,long minnum){

        if(!this.ret){
            return ;
        }
        if(root.left!=null){
            if(root.left.val>=root.val || root.left.val<=minnum){
                this.ret = false;
                return ;
            }
            this.dfs(root.left,root.val,minnum);
        }
        if(root.right != null){
            if(root.right.val<=root.val || root.right.val>=maxnum){
                this.ret= false;
                return ;
            }
            this.dfs(root.right,maxnum,root.val);
        }
    }
    
}

​

解题思路:

这道题是要让我们判断是否给定的treeNode是合格的二叉搜索树。

首先回顾一下二叉搜索树。二叉搜索树的左子树的各个节点均小于根节点，右子树的各个节点均大于根节点。根据这个性质我们就应该想到，在解决这道题时，每一次递归都需要传入最大值和最小值用于判断当前节点的值是否在两者之间，如果不在则该二叉树不是二叉搜索树。遍历了所有节点均满足要求后，则说明是二叉搜索树。