LeetCode 刷题记录: 98. Validate Binary Search Tree [Python]

原题

https://leetcode.com/problems/validate-binary-search-tree/

Given a binary tree, determine if it is a valid binary search tree (BST).

思路

递归判断子节点:

1. 当节点为None时，即到达分支底端，返回True即该条线正确。

2. 当min存在且当前值小于min时，返回False。

3. 当max存在且当前值大于max时，返回False。

4. 当不存在min和max时，开始往两头搜索。左边：最小值维持原样，最大值为当前节点的值。右边：最大值维持原样，最小值为当前节点的值。

   代码

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def isValidBST(self, root: TreeNode) -> bool: def search(root,mi,ma): if not root: return True if mi!=None and root.val<=mi: return False if ma!=None and root.val>=ma: return False return search(root.left,mi,root.val) and search(root.right,root.val,ma) return search(root,None,None)