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

忘是亡心i 2024-03-16 11:10 54阅读 0赞

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

### 题目 ###

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

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

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

示例 1：

![7bf6b2d8f320e42f68a0a9b89460aa72.png][]

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

示例 2：

![7edaa308f34dccbd1626a550d128106d.png][]

输入：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<=231−1

### 题解 ###

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

递归三要素：

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]` 为例：

![7fd369b3dabc9f9120a10da0e7ceb24a.png][]

右子树中的 `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 层，即二叉树退化成链表的时候。

[7bf6b2d8f320e42f68a0a9b89460aa72.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/2f9373d69bd342478693716d9025f14c.png
[7edaa308f34dccbd1626a550d128106d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/6338f85daa604ca5b7b2cb1f1990b997.png
[7fd369b3dabc9f9120a10da0e7ceb24a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/af25f428604f4473be84bec45e312298.png