作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
LeetCode解锁1000题: 打怪升级之旅
python数据分析可视化：企业实战案例
python源码解读
程序员必备的数学知识与应用
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给定一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树 (BST)。一个有效的 BST 定义如下：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
输入格式
- root：二叉树的根节点。
输出格式
- 返回布尔值，表示是否为有效的二叉搜索树。
示例
示例 1
输入: root = [2,1,3]
输出: True
解释: 给定二叉树是以下结构，显然是 BST:
2
/ \
1 3
示例 2
输入: root = [5,1,4,null,null,3,6]
输出: False
解释: 根节点的右子树包含比根节点小的值 (3 < 5)。
方法一：中序遍历
解题步骤
- 递归中序遍历：遍历树，确保遍历出的数值是递增的。
- 记录前一个节点值：使用一个变量记录前一个访问的节点值，比较当前节点值是否大于它。
完整的规范代码
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isValidBST(root):
"""
利用中序遍历验证二叉搜索树
:param root: TreeNode, 二叉树的根节点
:return: bool, 是否为有效的二叉搜索树
"""
prev = None
def inorder(node):
nonlocal prev
if not node:
return True
if not inorder(node.left):
return False
if prev is not None and node.val <= prev:
return False
prev = node.val
return inorder(node.right)
return inorder(root)
算法分析
- 时间复杂度：(O(n))，需要遍历树的所有节点。
- 空间复杂度：(O(h))，其中 (h) 是树的高度，代表递归栈的最大深度。
算法图解
对于问题 98 “验证二叉搜索树” 使用方法一中序遍历的过程，可以用 ASCII 图解来表示中序遍历的执行过程和节点值的检查。这种表示方式有助于直观地理解如何通过中序遍历确认一个树是否是二叉搜索树（BST）。中序遍历一个有效的 BST 应该产生一个递增的序列。
示例树结构
考虑一个简单的二叉树例子，以便我们可以展示中序遍历的过程：
2
/ \
1 3
此树的中序遍历结果应该是：1, 2, 3，这是一个递增序列。
ASCII 图解
这里是二叉树的节点及其遍历的 ASCII 表示：
步骤1: 访问根节点 2
步骤2: 移至左子节点 1
步骤3: 打印左子节点 1，回到根节点 2
步骤4: 打印根节点 2，移至右子节点 3
步骤5: 打印右子节点 3
ASCII 图表解释：
2 <- 根节点开始
/ \
1 3 <- 先访问左子树，然后根节点，最后右子树
中序遍历的步骤
通过中序遍历执行过程，我们可以追踪一个 “prev” 变量（先前访问的节点值），确保当前节点的值大于 “prev”。
中序遍历步骤：
1. 访问节点 2 的左子树（节点 1）
2. 访问节点 1，没有左子树，打印 1，记录 prev = 1
3. 返回到节点 2，prev = 1，当前节点 = 2，2 > 1 成立，打印 2，记录 prev = 2
4. 访问节点 2 的右子树（节点 3）
5. 访问节点 3，没有左子树，打印 3，记录 prev = 3
检查递增序列
每一步中，我们会检查当前节点值是否大于 “prev” 存储的值。如果这一条件在遍历过程中始终满足，那么这棵树是一个有效的二叉搜索树。
ASCII 动态展示
1 -> 2 -> 3 <- 中序遍历结果应该形成递增序列
使用 ASCII 图解来展示中序遍历的过程不仅增加了问题解决步骤的透明度，而且使得算法的验证步骤更加直观易懂，特别适合教学和解释复杂逻辑的场合。
方法二：递归验证
解题步骤
- 递归函数：检查每个节点是否满足左 < 当前 < 右的条件。
-
参数限制：使用参数
low和high限制节点值的有效范围。
完整的规范代码
def isValidBST(root):
def validate(node, low=float('-inf'), high=float('inf')):
if not node:
return True
if not (low < node.val < high):
return False
return validate(node.left, low, node.val) and validate(node.right, node.val, high)
return validate(root)
算法分析
- 时间复杂度：(O(n))，需要遍历每个节点。
- 空间复杂度：(O(h))，递归深度由树的高度决定。
方法三：迭代使用栈
解题步骤
- 使用栈：迭代地进行中序遍历。
- 检查顺序：确保从栈中弹出的节点值是递增的。
完整的规范代码
def isValidBST(root):
stack, prev = [], float('-inf')
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
if root.val <= prev:
return False
prev = root.val
root = root.right
return True
算法分析
- 时间复杂度：(O(n))，每个节点访问一次。
- 空间复杂度：(O(h))，栈的大小最多为树的高度。
不同算法的优劣势对比
| 特征 | 方法一：中序遍历 | 方法二：递归验证 | 方法三：迭代使用栈 |
|---|---|---|---|
| 时间复杂度 | (O(n)) | (O(n)) | (O(n)) |
| 空间复杂度 | (O(h)) | (O(h)) | (O(h)) |
| 优势 | 直观，易于理解 | 直接，逻辑清晰 | 避免递归，利于理解 |
| 劣势 | 依赖递归 | 可能过于复杂 | 管理栈稍复杂 |
应用示例
这些方法可以应用于任何需要验证二叉搜索树属性的场景，如数据库索引结构验证、自动化测试中的数据结构验证，或者作为其他算法的预处理步骤，如在进行BST相关的范围查询或平衡操作前验证其属性。