Leet Code OJ 98. Validate Binary Search Tree [Difficulty: Medium] -python

本文主要是介绍Leet Code OJ 98. Validate Binary Search Tree [Difficulty: Medium] -python，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

98. Validate Binary Search Tree

Medium

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

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

 

Example 1:

    2/ \1   3Input: [2,1,3]
Output: true

Example 2:

    5/ \1   4/ \3   6Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

题意：

题意就是判断该树是否为二叉树；二叉树特点：左孩子值比父节点的值小，右孩子的值比父节点的值大，并且不能相等。

思路：

一看就想到递归。怎么递归？递归的出口是到叶子节点，递归过程中判断条件就是判断左右孩子的值是否比父节点大或小。

递归过程分左右依次递归下去，更新每个节点的区间。

代码：

 

#98
# Definition for a binary tree node.
class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right
class Solution(object):def isValidBST(self, root):""":type root: TreeNode:rtype: bool"""return self.valid(root,float('-inf'),float('inf'))def valid(self,root,min,max):if not root:return Trueif root.val>=max or root.val<=min: #二叉树中不能存在值相等的节点，所以取等号return Falsereturn self.valid(rool.left,min,root.val) and self.valid(root.right,root.val,max)

 

这篇关于Leet Code OJ 98. Validate Binary Search Tree [Difficulty: Medium] -python的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---