力扣刷题TOP101: 27.BM34 判断是不是二叉搜索树

目录：

目的

思路

复杂度

记忆秘诀

python代码

目的：

给定一个二叉树根节点，请判断这棵树是不是二叉搜索树。

二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。

---

思路

什么是二叉搜索树（BST）？

• 每个节点的值必须比其左子树的所有节点值大。
• 每个节点的值必须比其右子树的所有节点值小。
• 也就是说，树中的每个节点都有一个范围（区间）约束。

---

• 主函数 isValidBST：

  • 入口函数，调用一个辅助函数 validate，开始递归检查整棵树是否满足 BST 的规则。

• 辅助函数 validate(node, low, high)：

  • 参数解释：
    • node：当前要检查的节点。
    • low：当前节点的值不能小于的最小值。
    • high：当前节点的值不能大于的最大值。
  • 功能：递归检查每个节点是否在合法范围内。

---

检查逻辑：

• 情况 1：节点为空。
  • 空节点不违反任何规则，所以直接返回 True。
• 情况 2：节点值不在范围内。
  • 如果节点的值小于 low 或大于 high，就返回 False。
• 情况 3：递归检查子树。
  • 检查左子树时，将 high 更新为当前节点值，因为左子树所有节点值必须小于当前节点值。
  • 检查右子树时，将 low 更新为当前节点值，因为右子树所有节点值必须大于当前节点值。

---

示例：

        5
       / \
      3   7
     / \
    2   4

初始调用：validate(5, -inf, inf)

• 节点值为5，范围是(-∞, ∞)，符合规则。
• 检查左子树：调用 validate(3, -inf, 5)。
• 检查右子树：调用 validate(7, 5, inf)。

递归检查左子树（以节点3为根）

1. 调用 validate(3, -inf, 5)：

   • 节点值为3，范围是(-∞, 5)，符合规则。
   • 检查左子树：调用 validate(2, -inf, 3)。
   • 检查右子树：调用 validate(4, 3, 5)。

2. 调用 validate(2, -inf, 3)：

   • 节点值为2，范围是(-∞, 3)，符合规则。
   • 左右子树为空，返回 True。

3. 调用 validate(4, 3, 5)：

   • 节点值为4，范围是(3, 5)，符合规则。
   • 左右子树为空，返回 True。

递归检查右子树（以节点7为根）

1. 调用 validate(7, 5, inf)：
   • 节点值为7，范围是(5, ∞)，符合规则。
   • 左右子树为空，返回 True。

最后结果

所有节点都符合规则，最终返回 True。

---

复杂度

• 时间复杂度：O(n）

  • 对每个节点只进行了访问一次，其中 n 是树中的节点数。

• 空间复杂度：O(n)

  • 递归调用栈的深度等于树的高度。
  • 在最坏的情况下（完全不平衡的树），空间复杂度为 O(n)。
  • 在最好的情况下（平衡的树），空间复杂度为 O(log n)。

---

记忆秘诀

• 通过递归和范围约束，逐步验证每个节点是否符合 BST 的规则。
• 每个节点的值必须在它的范围内，否则就返回 False。
  • 左子树的值范围是 (-∞, 当前节点值)，右子树的值范围是 (当前节点值, ∞)。

---

python代码

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        # 辅助函数，用于递归验证每个节点
        def validate(node, low=float('-inf'), high=float('inf')):
            # 如果当前节点为空，返回 True
            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)

---

* 欢迎大家探讨新思路，能够更好的理解和记忆

原文地址：https://blog.csdn.net/JiangTao2333/article/details/144357677

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！