Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a 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.

递归法

复杂度

时间 O(N) 空间 O(H) 递归栈空间

思路

递归的判断每个节点是否满足BST的要求，需要注意的是BST的要求不只是左节点小于根节点小于右节点，还有个隐含的条件是，左子树里所有节点都要小于根节点，而右子树里所有节点都要大于根节点。所以我们要把这个上限和下限代入递归中。

注意

• 这里的结构和不同的二叉树遍历一样，如果到空节点就返回，否则递归遍历左节点和右节点。唯一不同是加入了max和min，所以要在递归之前先判断是否符合max和min的条件。

• 不用再额外判断左右节点和根节点的关系，因为我们加入了max和min，如果左节点大于根节点的话，下一轮就过不了max的检查，右节点和min同理。

代码

public class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }
    
    private boolean isValidBST(TreeNode root, Integer max, Integer min){
        if(root == null){
            return true;
        }
        // 如果该节点大于上限 返回假
        if(max != null && root.val >= max){
            return false;
        }
        // 如果该节点小于下限 返回假
        if(min != null && root.val <= min){
            return false;
        }
        // 递归判断左子树和右子树
        return isValidBST(root.left, root.val, min) && isValidBST(root.right, max, root.val);
    }
}