题目

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

有效 二叉搜索树定义如下:

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

示例 1:

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

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

示例 2:

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

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

提示:

  • 树中节点数目范围在 [ 1 , 1 0 4 ] [1, 10^4] [1,104]
  • − 2 31 < = N o d e . v a l < = 2 31 − 1 -2^{31} <= Node.val <= 2^{31} - 1 231<=Node.val<=2311

题解

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

递归三要素:

  1. 递归函数:即根据定义判断是否满足条件:
  • 节点的左子树只包含 小于 当前节点的数。翻译成代码为 root.left.val < root.val
  • 节点的右子树只包含 大于 当前节点的数。翻译成代码为 root.right.val > root.val
  • 所有左子树和右子树自身必须也是二叉搜索树。翻译成代码为 isValidBST(root.left) && isValidBST(root.right)
  1. 边界条件:节点为空,直接返回true
  2. 还原现场:无需还原。

以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] 为例:

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

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

所以在判断子树是否满足条件的时候不仅要和当前节点的值做比较,还要和当前节点的父节点的值做比较。

假如根节点的取值范围为 ( − ∞ , + ∞ ) (-∞, +∞) (,+):

  1. 左节点left的取值范围就应该是(-∞, root.value)
  • 下一层左节点取值范围:(-∞, left.value)
  • 下一层右节点取之范围:(left.value, root.value)
  1. 右节点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)
    
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n), n n n 为节点个数,每个节点都要算一次,总共是 n n n 次。
  • 空间复杂度: O ( n ) O(n) O(n),空间复杂度为调用栈的深度,最多为 n n n 层,即二叉树退化成链表的时候。
05-30 23:57