【算法题解】32. 验证二叉搜索树的递归解发

❝

这是一道 「中等难度」 的题
https://leetcode.cn/problems/validate-binary-search-tree/

❞

题目

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

「有效」 二叉搜索树定义如下：

节点的左子树只包含 「小于」 当前节点的数。
节点的右子树只包含 「大于」 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3] 
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6] 
输出：false 解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在内

题解

根据有效二叉搜索树的定义，所有左子树和右子树自身必须也是二叉搜索树，然后子树的子树同样也需要满足是二叉搜索树，「一层一层往下走且每一层的判断条件都一样」，符合递归的的思路。

递归三要素：

递归函数：即根据定义判断是否满足条件：

节点的左子树只包含 「小于」 当前节点的数。翻译成代码为 root.left.val < root.val
节点的右子树只包含 「大于」 当前节点的数。翻译成代码为 root.right.val > root.val
所有左子树和右子树自身必须也是二叉搜索树。翻译成代码为 isValidBST(root.left) && isValidBST(root.right)

边界条件：节点为空，直接返回true。
还原现场：无需还原。

以Java代码为例：

class Solution {
    public boolean isValidBST(TreeNode root) {

        // 边界条件
        if(root == null){
            return true;
        }

        if(root.left != null && root.left.val >= root.val){
            return false;
        }

        if(root.right != null && root.right.val <= root.val){
            return false;
        }

        return isValidBST(root.left) && isValidBST(root.right);

    }
}

以上代码运行出错，以 [5,4,6,null,null,3,7] 为例：

右子树中的 3 小于 5，不满足定义的第二点：节点的右子树只包含 「大于」 当前节点的数。

所以在判断子树是否满足条件的时候不仅要和当前节点的值做比较，还要和当前节点的父节点以及父节点的父节点等等一直推算到根结点的所有值做比较。

假如根节点的取值范围为 :

那么左节点left的取值范围就应该是(-∞, root.value) ，

下一层左节点取值范围：(-∞, left.value)
下一层右节点取值范围：(left.value, root.value)

右节点right的取值范围就应该是(root.value, +∞)。

下一层左节点取值范围：(root.value, right.value)
下一层右节点取值范围：(right.value, +∞)

这样就可以将每一个节点的值当作边界值一层一层的传下去，并用于约束子节点的取值范围。

Java 代码实现

/**
 * 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 {
    public boolean isValidBST(TreeNode root) {
        // 因为节点值可以取Integer.MIN_VALUE  和 Integer.MAX_VALUE，
        // 所以正负无穷的值必须 大于Integer.MAX_VALUE 和 小于Integer.MIN_VALUE

        // 根结点的取值范围在正负无穷之间
        return this.isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);

    }

    /**
    * @param minVal 最小值，不包含
    * @param maxVal 最大值，不包含
    */
    private boolean isValidBST(TreeNode node, long minVal, long maxVal) {
        // 边界条件
        if(node == null){
            return true;
        }

        // 判断节点值是否满足取值范围
        if(node.val >= maxVal || node.val <= minVal){
            return false;
        }

        // 左节点的值必须在父节点的取值范围内且需要小于父节点的值
        // 右节点的值必须在父节点的取值范围内且需要大于父节点的值
        return isValidBST(node.left, minVal, node.val) && isValidBST(node.right, node.val, maxVal);
    }
}

Go 代码实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    return isValidBST2(root, math.MinInt64, math.MaxInt64)
}

func isValidBST2(root *TreeNode, minVal int, maxVal int) bool {
    if root == nil {
        return true
    }

    if root.Val >= maxVal || root.Val <= minVal {
        return false
    }

    return isValidBST2(root.Left, minVal, root.Val) && isValidBST2(root.Right, root.Val, maxVal)
    
}