题解 | #判断是不是二叉搜索树#

秒懂【二叉搜索树验证】！递归一步步拆解。

1.思路

先来看二叉搜索树的性质：

二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树，其每个节点的值都大于其左子树中所有节点的值并且小于其右子树中所有节点的值。二叉搜索树允许快速查询、插入和删除操作，多数操作（插入、删除和查找）的时间复杂度都是O(log n)。

以下是二叉搜索树的一些基本特性：

1.左子树的所有节点的值都小于其父节点。

2.右子树的所有节点的值都大于其父节点。

3.左、右子树也必须是二叉搜索树。

4.每个节点只有一个父节点（除了根节点）和最多两个子节点（左子节点和右子节点）。

判断一颗二叉树是否为二叉搜索树依赖于树的左右子树。可以采用递归的方法。

先来看看是否满足递归的两个条件：

可以看出，判断二叉树是否为二叉搜索树的求解满足递归的两个条件，因此可以采用递归的方法进行求解。

一颗二叉树是否为二叉搜索树依赖于节点的左右子树。对于左子树，取值范围为：（-∞，root.val]；对于右子树，取值范围为： [root.val,+∞)。因此对应的递推公式如下：

有了递推公式，就可以很方便的写出对应的代码。

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

2.代码

2.1 Python代码

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @return bool布尔型
#
import sys
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        # write code here
        return self.recursion(
            root, -sys.maxsize - 1, sys.maxsize
        )  # 对于二叉树来说，取值范围为：(-∞,+∞)

    def recursion(self, root, min_value, max_value):
        # 2. 递归终止条件:
        # 2.2 如果二叉树为空，是搜索二叉树
        if root is None:
            return True
        # 2.2 如果当前节点的值小于min或者 大于max，则不是二叉搜索树
        if root.val <= min_value or root.val >= max_value:
            return False

        # 1. 问题分解（递推公式）
        # 左子树取值范围：(min,root.val]；	右子树取值范围：[root.val,max)
        return self.recursion(root.left, min_value, root.val) and self.recursion(
            root.right, root.val, max_value
        )

2.2 Java代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return bool布尔型
     */
    public boolean isValidBST (TreeNode root) {
        // write code here
        return recursion(root, Integer.MIN_VALUE,
                         Integer.MAX_VALUE);//对于二叉树来说，取值范围为：(-∞,+∞)
    }

    private boolean recursion(TreeNode root, int min, int max) {
        // 2. 递归终止条件:
        // 2.2 如果二叉树为空，是搜索二叉树
        if (root == null) {
            return true;
        }
        // 2.2 如果当前节点的值小于min或者 大于max，则不是二叉搜索树
        if (root.val <= min || root.val >= max) {
            return false;
        }


        // 1. 问题分解（递推公式）
        //左子树取值范围：(min,root.val]； 右子树取值范围：[root.val,max)
        return recursion(root.left, min, root.val) &&
               recursion(root.right, root.val, max);
    }
}

2.3 Go代码

package main

import (
	"math"
)

import . "nc_tools"

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @return bool布尔型
 */
func isValidBST(root *TreeNode) bool {
	// write code here
	return recursion(root, math.MinInt32, math.MaxInt32) //对于二叉树来说，取值范围为：(-∞,+∞)
}

func recursion(root *TreeNode, min int, max int) bool {
	// 2. 递归终止条件:
	// 2.2 如果二叉树为空，是搜索二叉树
	if root == nil {
		return true
	}
	// 2.2 如果当前节点的值小于min或者 大于max，则不是二叉搜索树
	if root.Val <= min || root.Val >= max {
		return false
	}

	// 1. 问题分解（递推公式）
	//左子树取值范围：(min,root.val]；	右子树取值范围：[root.val,max)
	return recursion(root.Left, min, root.Val) && recursion(root.Right, root.Val, max)
}

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解：B站@好易学数据结构