给定一个二叉树,判断其是否是一个有效的二叉搜索树

东白随记
0 评论
/ /
0 阅读
/
1211 字
17 2024-09

要判断一个二叉树是否是一个有效的二叉搜索树(Binary Search Tree,简称BST),我们需要检查该二叉树的节点是否满足BST的特性。BST的特性是:对于树中的任意节点,其左子树的所有节点值都小于该节点的值,其右子树的所有节点值都大于该节点的值。

以下是一个简单的Python算法来检查一个二叉树是否为有效的BST:

```python

class TreeNode:

def __init__(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

def isValidBST(root):

def helper(node, lower=float('-inf'), upper=float('inf')):

if not node:

return True

# 判断当前节点的值是否在规定的范围内

if node.val <= lower or node.val >= upper:

return False

# 递归地检查左子树和右子树

return (

helper(node.left, lower, node.val) and # 左子树中所有节点值小于当前节点值

helper(node.right, node.val, upper) # 右子树中所有节点值大于当前节点值

)

return helper(root)

```

在上面的代码中,`isValidBST`函数会调用一个辅助函数`helper`。这个辅助函数以一个二叉树的节点、以及两个限制范围作为参数。如果当前节点为空,那么它就是一个有效的BST。否则,我们需要检查当前节点的值是否在规定的范围内(即大于`lower`且小于`upper`)。然后,我们递归地检查左子树和右子树是否也满足BST的特性。如果所有的递归调用都返回`True`,那么这个二叉树就是一个有效的BST。

注意:上述代码假设二叉树中没有重复的节点值。如果允许有重复的节点值,那么定义BST的规则可能会稍有不同。