判断二叉排序树的代码

Terence888

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        self.pre = None
        def isBST(root):
            if not root:
                return True
            if not isBST(root.left):
                return False
            if self.pre and self.pre.val >= root.val:
                return False
            self.pre = root
            #print(root.val)
            return  isBST(root.right)
        return isBST(root)
        

帮我解读一下，递归挺乱的

FishC

当然可以！这段代码是用递归判断一个二叉树是否为二叉搜索树（BST）的。

### 代码解读：

1. **初始化 `self.pre`**：
   - 用于记录中序遍历中上一个访问的节点，初始化为 `None`。

2. **递归函数 `isBST(root)`**：
   - **基准情况**：如果当前节点为空（`not root`），返回 `True`（认为空树为BST）。

3. **递归左子树**：
   - 对左子树进行递归调用 `isBST(root.left)`。
   - 如果左子树不是BST，立即返回 `False`。

4. **检查当前节点**：
   - 如果 `self.pre` 存在，并且 `self.pre.val >= root.val`，说明当前节点值不符合BST的性质（中序遍历时应递增），返回 `False`。

5. **更新 `self.pre`**：
   - 将当前节点设为 `self.pre`，用于下一次中序比较。

6. **递归右子树**：
   - 对右子树进行递归调用 `isBST(root.right)`。
   - 判断右子树是否为BST。

7. **最终返回**：
   - 结合整个递归过程，最终判断整棵树是否为BST。

通过中序遍历，检查每个节点的值是否递增来判断BST的合法性。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。